一、HashMap简介
1、HashMap底层是哈希表结构,类似字典,初始化如下:
2、哈希表结构:
是一个数组+单向链表的结构体
数组:查询效率较高,随机增删效率很低
单向链表:在随机增删方面效率较高,查询方面效率很低
哈希表将以上两种数据结构融合在一起,充分发挥它们各自的优点。
3、HashMap集合底层是数组,Node<k,v>[]tables;
hash为哈希值,是HashCode方法执行的结果,通过哈希算法可以转换为数组的下标;
key,value为Map的key与value,next为下一个内存地址
4、map.put(k,v)的实现原理
k,v封装到Node对象内,底层调用hashCode()方法得出hash值,通过哈希算法/哈希函数,将hash值转换成数组下标。
如果下标对应的位置上面没有元素,Node添加到位置上;
如果下标对应的位置上有链表,拿k与链表每个节点k进行equals,如所有equals方法都false,新节点将添加到尾部;
如果有一个euals返回true,那么这个节点的value值将会覆盖
5、map.get(k)的实现原理
调用k的hashCode()方法得出哈希值,通过哈希算法转换成数组下标,通过数组下标快速定位到某个位置,位置上什么都没有话,返回null;
如果这个位置上有单向链表,那么会拿着参数k和单向链表上每个节点的k进行equals,如果所有的equals返回false,囊二get方法返回null。
主要其中某一个节点的k和参数k equals返回true,那么此时这个节点的value就是我们要找的value,既为get方法的最终返回value
6、HashMap的key部分元素需要重写equals方法hashCode方法。也就是hashSet集合中的元素需要重写equals方法hashCode方法。
7、HashMap使用不当时会发生性能问题:
假设所有的hashCode方法返回值都相等,那么底层会变成单向链表,即散列分布不均匀。
什么是散列分布均匀:100个元素,10个单向链表,每个单向链表中包含10个节点。
假设所有的hashCode方法返回均不一样,那么底层会变成数组,即散列分布不均匀。
散列分布均匀需要重写hashCode方法有一定的技巧
8、HashMap集合底层数组达到75%容量时,数组是开始扩容,默认数组容量为16,初始化容量必须是2的倍数,为达到散列分布均匀,且可以提高hashMap集合存取效率。
9、HashMap元素存取什么时候不需要执行equals方法:k.hashCode方法返回的哈希值的数组下标位置为null的时候,equals不再需要执行。
10、HashMap JDK8改进:
如果哈希表的单向链表中元素>8,单向链表会变成红黑树,当红黑树上节点数量<6,会重新把红黑数变成单向链表
11、哈希表数据结构注意事项:
如果o1与o2的hash值相同,一定在同一个单向链表上,
如果o1与o2的hash值不同,但由于哈希算法执行结束后转换的数组下标可能相同,此时会发生“哈希碰撞”
二、实例说明:
1、测试HashMap元素特点:key为integer,它的hashCode与equals均已经被重写
2、遍历Map集合-元素将被无须取出
3、重写quals与hashCode方法
未重写hashCode与equals
重写hashCode与equals后
4、HashMap的key与value可以为空吗,
HashMap可以,Hashtable则不行