Moosphan/Android-Daily-Interview

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

Moosphan opened this issue · 8 comments

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

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

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

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

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

20180423002750407

①.判断键值对数组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，如果超过，进行扩容。

更多可参考以下文章：

  • 👍9
  • 🎉1
manondidi commented

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

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

  • 👍1
  • 😄13
Alex-Cin commented

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

  • 👍14
manondidi commented

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

  • 😄1
Petterpx commented

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

MicroKibaco commented

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

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

  • 👍1
kuye910 commented

HashMap

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

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

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

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

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

  • 👍1