程序员必须知道的数据结构:HashMap 与 LinkedHashMap
为什么要说 HashMap 与 LinkedHashMap?第一:这两种数据结构是 Java Coder 中经常使用的数据结构、第二:这两种结构是最合适的能说明链表与数组的结构关系。在开始之前首先必须清楚一个概念,什么是 hash 值?hash 值是指将一个二进制的值通过 hash 算法将其转换成一个固定长度的二进制的值。
我们通常使用的 Map 结构是通过什么方式存储数据的?它是通过数组与链表结合的形式来进行数据存储的。在前面小节的说明中我们知道,线性表的查询速度是比较快的、链表的插入速度是比较快的。而 Map 就是将两者结合起来,数据结构外围使用数组、内部使用链表的形式来存储数据,通过 hash 值来实现寻址快速、插入相对快速的效果,下面通过图片来看一下 hash 表中常见的数据结构展示 -- 拉链法。
这种形式的存储结构就是我们平常所使用的 HashMap 的数据结构,如图中,0~12 组成一个数组,每个位置中又存放着一个链表,而链表中的每个数据对象内部又是通过键值对的形式来存放数据元素的。
这张图展示的是 LinkedHashMap 的数据结构图,和 HashMap 不同的是,它的链表里面的数据元素存储是有序的。其中最大的不同就是 LinkedHashMap 是一个双向链表,如果在使用时数据结构比较复杂(比如:一层又包含着一层的数据对象)、要求效率比较高的话,最好使用 LinkedHashMap,可以使用下面代码解决 LinkedHashMap 线程不同步的问题。
同样,HashMap 也是线程不同步的,也可以使用 Collections.synchronizedMap() 方法来使线程安全,在 Jdk1.8 之后增加的 ConcurrentHashMap 实例是线程安全的,如果高版本尽量使用这种方式。
更多精彩前往微信公众号【老王说编程】>>>
版权声明: 本文为 InfoQ 作者【老王说编程】的原创文章。
原文链接:【http://xie.infoq.cn/article/7e2137a95214f609511155980】。文章转载请联系作者。
评论