Hash表Node[]存储结构图。
Hash表 Node[] 存储结构图
HashMap存储结构是由数组+链表组成的。
数组 ：数组的存储区是连续的，占用内存严重，故空间复杂度很大。但数组的二分查找时间度小；数组的特点：寻址容易，插入和删除困难
链表 ：链表的储存区离散，占用内存比较宽松，故空间复杂度很小，但时间复杂度大；链表的特点：寻址困难，插入和删除容易。
哈希表 Node[]中包含包含链表。HashMap综合了数组跟链表的优点。
1.分析存储结构，及如何解决hash冲突
先看下源码
jdk 1.8版本，用于存储数组对象为 Node[]，Node 实现了Map.Entry<K,V>
老版本为Entry[]
···
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
}
···
···
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;//计算坐标
if ((p = tab[i = (n - 1) & hash]) == null)//如果此坐标未使用，直接存储在此位置
tab[i] = newNode(hash, key, value, null);
else {//否则使用链表存储
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;//覆盖
else if (p instanceof TreeNode)//已经不是第一次Hash冲突了，在链表中新增
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {//首次hash冲突
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);//使用链表存储
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
···
}
- 如何解决Hash冲突呢？
Node类有一个next属性，作用是指向下一个Node。打个比方， 第一个键值对A进来，通过计算其key的hash得到的index=0，记做:Node[0] = A。一会后又进来一个键值对B，通过计算其index也等于0，现在怎么办？HashMap会这样做:B.next = A,Node[0] = B,如果又进来C,index也等于0,那么C.next = B,Node[0] = C；这样我们发现index=0的地方其实存取了A,B,C三个键值对,他们通过next这个属性链接在一起。所以疑问不用担心。也就是说Node[]数组中存储的是最后插入的数据
读取
有了上面存储的分析，读取这块就简单明了。
简单描述：根据计算坐标取出 哈希表中的指定元素。如果key匹配，则返回。否则继续判断是否是 TreenNode，是则遍历此链表，匹配key 并返回
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
if ((e = first.next) != null) {
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
几个Map实现类对比总结
-
HashMap
- key 用 Set 存放，所以想做到 key 不允许重复，key 对应的类需要重写 hashCode 和 equals 方法
- 允许空键和空值（但空键只有一个，且放在第一位，下面会介绍）
- 元素是无序的，而且顺序会不定时改变（发生Hash冲突时，导致链表元素移动）
- 插入、获取的时间复杂度基本是 O(1)（前提是有适当的哈希函数，让元素分 * 布在均匀的位置）
- 遍历整个 Map 需要的时间与 桶(数组) 的长度成正比（因此初始化时 * HashMap 的容量不宜太大）
-
TreeMap
- 有序的
-
LinkedHashMap
- 结合 HashMap 和 TreeMap 的有点，有序的同时效率也不错，仅比 HashMap 慢一点
-
支持同步的几个Map
- SynchronizedMap
- ConcurrentHashMap
- Hashtable
斟酌了以下，之所以没有在api上细扣，因为理解原理更重要，而且理解一种思维以后不容易忘，api的话今天做笔记，明天不忘后天也忘了，还不一定用得到。
兴趣使然，总之加油吧～
END
参考博客：
https://blog.csdn.net/junchenbb0430/article/details/78643100
https://blog.csdn.net/liweizhong193516/article/details/77416073
https://blog.csdn.net/u011240877/article/details/53351188
https://blog.csdn.net/hwz2311245/article/details/51454686
网友评论