java HashMap

电脑

intellij IDEA

什么是HashMap？1、基于哈希表的一个Map接口实现，存储的对象是一个键值对对象(Entry)；2、基于数组和链表实现，内部维护着一个数组table，该数组保存着每个链表的表头结点；查找时，先通过hash函数计算key的hash值，再根据key的hash值计算数组索引（取余法），然后根据索引找到链表表头结点，然后遍历查找该链表；

HashMap数据结构1、画了个示意图，如下，左边的数组索引是根据key的hash值计算得到，不同hash值有可能产生一样的索引，即哈希冲突，此时采用链地址法处理哈希冲突，即将所有索引一致的节点构成一个单链表；

HashMap继承的类与实现的接口1、HashMap接口示意图：如下所示2、Map接口，方法的含义很简单，基本上看个方法名就知道了，后面会在HashMap源码分析里详细说明3、AbstractMap抽象类中定义的方法

HashMap  是如何存储的？a.底层是一个数组 tabb. hash=hash(key) ，然后根据数组长度n和hash值，决定当前需要put的元素对应的数组下标，hash算法见红框。

数组长度是固定的，HashMap 可以无限put(k,v) ,为什么？HashMap  的元素个数大于threshold的时候，会进行resize() 扩容

如何实现扩容的？扩容就是通过 resize() , 重新创建一个新数组，对所有元素rehash,放到新数组相应位置。扩容代价是很大的，编码规范都有一条，合理设置hashMap的InitialCapicity,禁止直接用HashMap()

Hash 冲突是什么？怎么解决这个问题？1、Hash 冲突： 假如一个学校有366个同学，一年365天，那么至少有两个同学是同一天生日，这就是hash冲突。用代码来说，不同的key 经过计算p = tab[i = (n - 1) & hash] 对应同一个p2、如何解决:p在有的翻译文档中叫桶，一个桶可以装多个，怎么装? 链表或者红黑树。3、下图代码中 else if 部分是红黑树else 部分是链表 ，链表中如果冲突元素个>=TREEIFY_THRESHOLD-1,会将链表转换成红黑树。因为元素个数很多时，红黑树比链表性能更好。

HashMap 是不是线程安全的，如何解决线程安全问题？1、HashMap 是线程不安全的2、对整个map加锁。3、如图（3）对f加锁了，就是对桶加锁，就是传说中的分段锁机制。在保证安全的前提下，加锁的范围越小，则程序性能越高，自己写代码时切记胡乱在方法上加synchronized

HashMap 和 hash()  equals() 方法的关系1、面试中面试官会问重写equals()方法要注意是什么，答案是hash()也要重写。不重写会引起HashMap 等集合类使用的混乱。2、如下图：比如类Person(id,name)，重写了 equals(Object obj){... reutrn this.id==obj.id}，没有重写hash(), 那么从类定义上来说，只要id相等就是同一个人，当我们Person作为key，放入两个Person对象(id相等)到HashMap的时候，那么就翻车了，HashMap 会有两个元素，而我们期望的只保留一个。

验证ConcurrentHashMap 线程安全。