HashMap、LinkedHashMap 学习笔记
HashMap
来看一下 HashMap 的特点:
HashMap 的键必须是唯一的,不能重复。
HashMap 的键允许为 null,但只能有一个这样的键;值可以有多个 null。
HashMap 是无序的,它不保证元素的任何特定顺序。
HashMap 不是线程安全的;多线程环境下,建议使用 ConcurrentHashMap,或者使用
Collections.synchronizedMap(hashMap)
将 HashMap 转成线程同步的。只能使用关联的键来获取值。
HashMap 只能存储对象,所以基本数据类型应该使用其包装器类型,比如说 int 应该为 Integer。
HashMap 实现了 Cloneable 和 Serializable 接口,因此可以拷贝和序列化。
HashMap 有 5 个重要的字段
HashMap 的 Hash 算法
Hash,把任意长度的数据通过一种算法映射到固定长度的域上(散列值)。
HashMap 的底层数据结构是一个数组,不管是增加、删除,还是查找键值对,定位到数组的下标非常关键。 HashMap 是通过什么样的方法来定位下标呢?
>>>
为无符号右移运算符,高位补 0,移多少位补多少个 0
^
为异或运算符,其运算规则为 1^0 = 1、1^1 = 0、0^1 = 1、0^0 = 0。
&
为按位与运算符,运算规则是将两边的数转换为二进制位,然后运算最终值,运算规则即(两个为真才为真)1&1=1、1&0=0、0&1=0、0&0=0。
k.hashCode()
用来计算键的 hashCode 值。对于任意给定的对象,只要它的 hashCode()
返回值是相同,那么 hash()
方法计算得到的 Hash 码就总是相同的。
要能够做到这一点,就要求作为键的对象必须是不可变的,并且 hashCode()
方法要足够的巧妙,能够最大可能返回不重复的 hashCode 值,比如说 String 类。
put()
计算后的 hash 值冲突了怎么办?put()
方法会先调用 hash()
方法计算 key 的 hash 值,然后再调用内部方法 putVal()
:
如果哈希冲突的话,会执行 ② 处对应的 else 语句,先判断键是否相等,相等的话直接覆盖;否则执行 ④,做红黑树处理;如果不是,会执行 ⑤,把上一个节点的 next 赋值为新的 Node。
也就是说,如果哈希冲突了,会在数组的同一个位置上增加链表,如果链表的长度大于 8,将会转化成红黑树进行处理。
简单点说,就是数组加链表,由于链表的查询效率比较低(时间复杂度为 ),Java 8 又追加了红黑树(时间复杂度为 )。
get()
首先计算 key 的 hash 值,当 hash 值确定后,键值对在数组中的下标位置也就确定了,然后再调用 getNode()
方法:
其中 first = tab[(n - 1) & hash]
就可以快速的确定键对应的值,如果键相等并且键的 hash 相等,则直接返回;如果键的哈希冲突了,就先判断是不是红黑树,不是的话就遍历链表。
LinkedHashMap
插入顺序
LinkedHashMap.Entry 继承了 HashMap.Node,并且追加了两个字段 before 和 after
LinkedHashMap 在添加第一个元素的时候,会把 head 赋值为第一个元素,等到第二个元素添加进来的时候,会把第二个元素的 before 赋值为第一个元素,第一个元素的 after 赋值为第二个元素。
HashMap#put
LinkedHashMap 重写 newNode 方法
访问顺序
访问包括调用 get()
方法、remove()
方法和 put()
方法。最不经常访问的放在头部,使用 LinkedHashMap 来实现 LRU(Least Recently Used) 缓存。
重写 removeEldestEntry
维护访问顺序
哪个元素被访问,哪个元素就放到最后
LinkedHashMap 实现 LRU,在插入元素的时候,需要调用 put()
方法,该方法最后会调用 afterNodeInsertion()
方法,这个方法被 LinkedHashMap 重写了。removeEldestEntry()
方法会判断第一个元素是否超出了可容纳的最大范围,如果超出,那就会调用 removeNode()
方法对最不经常访问的那个元素进行删除。
评论