2019-03-29：HashMap 的实现原理？

Moosphan commented 5 years ago

HashMap 实际上是一个“链表散列”的数据结构，即数组和链表的结合体。它是基于哈希表的 Map 接口的非同步实现。

数组：存储区间连续，占用内存严重，寻址容易，插入删除困难；
链表：存储区间离散，占用内存比较宽松，寻址困难，插入删除容易；
Hashmap 综合应用了这两种数据结构，实现了寻址容易，插入删除也容易。

例如我们以下图为例，看一下 HashMap 的内部存储结构： c3d16ff23e8306901065975abd10921a

关于 HashMap 的存取过程，可参照下图：

①.判断键值对数组table[i]是否为空或为null，否则执行resize()进行扩容； 
②.根据键值key计算hash值得到插入的数组索引i，如果table[i]==null，直接新建节点添加，转向⑥，如果table[i]不为空，转向③； 
③.判断table[i]的首个元素是否和key一样，如果相同直接覆盖value，否则转向④，这里的相同指的是hashCode以及equals； 
④.判断table[i] 是否为treeNode，即table[i] 是否是红黑树，如果是红黑树，则直接在树中插入键值对，否则转向⑤； 
⑤.遍历table[i]，判断链表长度是否大于8，大于8的话把链表转换为红黑树，在红黑树中执行插入操作，否则进行链表的插入操作；遍历过程中若发现key已经存在直接覆盖value即可； 
⑥.插入成功后，判断实际存在的键值对数量size是否超多了最大容量threshold，如果超过，进行扩容。

更多可参考以下文章：

manondidi commented 5 years ago

这题其实很难,hashmap是一个key value 存储的数据结构 jdk8对hashmap做了优化,在长度小于8个时候是链表的数据结构超过8个的时候转换成红黑树

至于红黑树,听说字节跳动面试常问这个问题,一种很复杂的数据结构,我不会

Alex-Cin commented 5 years ago

讲到HashMap, 我简单描述一下会问到的问题哦:
1.. 扩容算法, 时间复杂度是多少, 你了解到它实现的原理吗?
2.. 是先扩容还是优先树化;
3.. 有听说过 ArrayMap吗, 为什么ArrayMap会节省内存; (TIPS 稀疏数组, 包装类占据内存);
4.. 和LinkedHashMap有什么区别, Linked怎么做到的访问顺序问题;
5.. LRUCache了解多少?
6.. 对 ConcurrentHashMap 了解吗?

manondidi commented 5 years ago

什么是红黑树就没几个人会

Petterpx commented 5 years ago

首先说到HashMap，你必须要知道它是数组加链表构成的。那为什么是呢？然后要对什么是桶(Socket)了解。了解它的几个重要属性：负载因子，容量，扩容阈值然后了解它的put方法，Hashcode的计算方法，及哈希碰撞之后的处理方式，也就是了解链表与红黑树的过程。然后需要了解它的扩充原理，为什么要扩充两倍。。。后面就差不多了，哈哈

MicroKibaco commented 5 years ago

HashMap 是应用更加广泛的哈希算表实现,行为上与HashTable一致,主要区别在于与HashMap 不是同步的,支持null键和值等.通常情况下,Hashmap进行 put 或get 操作,可以达到常数时间的性能,所以他是绝大部分利用键值对存取场景的首选,比如,实现一个用户ID 和用户信息对应的运行时存储结构,HashMap 等其他 Map 都扩展了 AbstractMap,这里面包含了通用方法抽象.不同Map的用途,从类图结构就能体现出来,设计已经体现在不同接口上了,大部分使用Map的场景就是放入,访问或者删除,对顺序没有特别的要求,HashMap在这种情况基本上是最好的选择.HashMap的性能表现非常依赖于哈希码的有效性,请务必掌握hashCode和equals的一些基本约定:

equals相等,hashCode一定相等
重写equal一定要重写equals
hashCode 需要保持一致性,让状态改变返回的哈希值仍然要一致
equals的对称,反射,传递等特性 HashMap的源码分析: 首先我们一起来看一看HashMap的内部结构,他可以看做数组(Node<K,V> table)和链表结合组合的复合结构,数组被分为一个个桶(bucket),通过Hash值决定键值对在数组的寻址;哈希值相同的键值对,则以链表形式存储

RealMoMo commented 5 years ago

Java中HashMap底层实现原理(JDK1.8)源码分析 https://blog.csdn.net/tuke_tuke/article/details/51588156

kuye910 commented 2 years ago

HashMap

没有synchronized修饰、线程不安全、Key和Value都可以为null

底层实现：数组+链表在JDK8开始，链表高度如果达到8，数组长度达到64，链表就会变成红黑树，元素会以内部类Node的形式存在；

1、计算Key的hash值，二次hash然后对数组的长度进行取模，对应到数组的下标

2、如果没有出现hash冲突，则直接创建存入Node数组

3、如果产生hash冲突，先进行equal比较，相同就取代该元素，如果不同，则判断链表高度插入链表，链表高度达到8，并且数组长度达到64，则转变成红黑树，低于64则变回链表；

Moosphan / Android-Daily-Interview

2019-03-29：HashMap 的实现原理？ #16

HashMap