一, Map 的实现类的结构
1.Map: 双列数据, 存储 key-value 对的数据
1.1HashMap
作为 Map 的主要实现类; 线程不安全, 效率高, 可以存储 null 的 key 和 value.
底层: 数组 + 链表(jdk7 及之前); 数组 + 链表 + 红黑树(jdk8)
1.1.1 LinkedHashMap
保证在遍历 map 元素时, 可以按照添加的顺序实现遍历, 原因: 在原有的 HashMap 底层结构基础上, 添加了一对指针, 只想前一个和后一个元素.
对于频繁的遍历操作, 执行效率高于 HashMap.
1.2 TreeMap
保证按照添加的 key-value 对进行排序, 实现排序遍历, 此时考虑 key 的自然排序或定制排序
底层使用红黑树
1.3 Hashtable
作为古老的实现类, 线程是安全的, 效率低, 不能存储 null 的 key 和 value
1.3.1 Properties
常用来处理配置文件, key 和 value 都是 String 类型
二, Map 结构的理解
Map 中的 key: 无序的, 不可重复的, 使用 Set 存储所有的 key -> key 所在的类要重写 equals()和 HashCode()方法(以 HashMap 为例)
Map 中的 value: 无序的, 可重复的, 使用 Collection 存储所有的 value -> value 所在的类要重写 equals()
一个键值对: key-value 构成了一个 Entry 对象
Map 中的 Entry: 无序的, 不可重复的, 使用 Set 存储所有的 Entry
三, HashMap 的底层实现原理(jdk7)
1.HashMap map = new HashMap();
在实例化以后, 底层创建了长度是 16 的一维数组, 类型为 Entry[]名字为 table.
2.map.put(key1,value1);
首先, 调用 key1 所在类的 hashCode()计算 key1 哈希值, 此哈希值经过某种算法计算之后, 得到在 Entry 数组中的存放位置.
如果此位置上数据为空, 此时添加成功.------- 情况 1
如果此位置上的数据不为空(意味着此位置上存在一个或多个数据<以链表形式存在>), 比较 key1 和已经存在的一个或多个数据的哈希值:
如果都不相同, 此时添加成功.-------- 情况 2
如果和某一个已经存在的数据 (key2,value2) 的哈希值相同, 继续比较: 调用 key1 所在类的 equals(key2)方法, 比较:
如果返回 false: 添加成功. -------- 情况 3
如果返回 true: 使用 value1 替换 value2.
补充: 关于情况 2 和情况 3, 此时 key1-value1 和原来的数据以链表的形式存储.
3. 在不断的添加过程中, 会涉及到扩容问题, 当超出临界值且存放的位置非空时进行扩容, 默认的扩容方式, 扩容为原来的 2 倍, 并将原有的数据复制过来.
jdk8 相较 jdk7 的不同:
1.new HashMap(): 底层没有创建一个长度为 16 的数组, 首次调用 put()时才创建
2.jdk8 底层的数组是 Node[]而不是 Entry[]
3.jdk8 中的底层结构: 数组 + 链表 + 红黑树
当数组的某一个索引位置上的的元素以链表形式存在的数据个数 > 8 且当前数组的长度 > 64 时, 此时索引位置上的所有数据改为用红黑树存储, 提高比较时的效率
来源: http://www.bubuko.com/infodetail-3655430.html