HashMap基本概念
- 允许null value和null key
- 不保证所有key的遍历顺序
- 如果没有hash冲突,put和get操作的时间复杂度是O(1)
- 对HashMap遍历的时间复杂度是O(m + n),其中m是bucket个数,n是元素个数
- 装载因子(load factor) 用于判断HashMap何时扩容。元素个数n 大于等于capacity * load factor,则会扩容;从而保证bucket个数维持在元素个数的2倍左右。
- load factor默认值是0.75,调大可以节省空间,但是查询速度变慢;
- HashMap不是线程安全的
- 默认采用拉链表,但是当一个链表中的节点数过多时,转换为树结构(类似于TreeMap中的结构,红黑树),以加快hash冲突情况下的查询速度。
- 只有当拉链表table的大小超过一定值时,才会开始创建红黑树。
- 红黑树中的节点按照hash code排序,如果hash code相同,看是否实现了相同的Comparable接口,如果实现了则根据Comparable接口判断顺序(这里尼玛用到了反射)
- 当红黑树中的节点数低于一定值,则退化回链表。
- bucket个数一定是2^n,因为:1)用2^n – 1与hash code进行位运算可直接找到bucket;2)每次扩容是把bucket个数扩大2倍,原来的hash code要么位置不变,要么往后移动2^(n-1)个位置。缺点:如果hash函数在生成hash code的时候,只利用了低比特位,则寻找bucket位置容易导致hash冲突,例如把Float类型作为key存入hashmap,且float数字是连续整数。如何解决?hash code高比特位与低比特位再进行一次异或位运算。
final void putMapEntries(Map extends K, ? extends V> m, boolean evict)
实现:根据参数Map的大小判断是否需要扩容,然后调用putVal。用于实现putAll操作。
public int size()
实现:直接返回size
public boolean isEmpty()
实现:判断size是否等于0.
public V get(Object key)
实现:直接调用getNode实现
final Node
实现:先用hash值找到table入口,然后比较key与根节点,如果根节点hash不匹配,则分别针对红黑树和链表执行一次查找操作。
public boolean containsKey(Object key)
实现:直接调用getNode,返回null则返回false,否则true。
public V put(K key, V value)
实现:直接调用putVal。
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict)
实现:如果table为空则先扩容,然后根据hash值找到入口。如果入口位置为空,则直接创建一个Node放在数组的这个位置;如果入口不为空,则判断key是否是重复put(幂等性),是重复put则直接返回,不是则继续。然后根据hash值查找原节点,找到节点则直接修改value;如果没找到,对于红黑树触发红黑树插入节点操作;对于链表,在链表末尾插入Node(JDK 1.7是在链表的头部插入,多线程环境下访问易引发死循环)。
final Node
说明:用于对HashMap进行扩容。
实现:首先根据容量、装载因子、threshold计算扩容大小,然后创建table数组,把原table中的Node逐个存入新table。转移数据的时候,如果原table中的一个bucket只有一个节点,则直接放入新table;如果是一个红黑树,则触发红黑树split操作;如果是一个链表,则原来的一个链表会被拆成2个链表(因为模运算的底数变了),分别放入新table的两个位置,且在2个新链表中,Node的相对顺序与原来保持一致。
final void treeifyBin(Node
如果table长度小于8,则扩容;如果大于8,则根据hash值找到table入口,然后遍历链表,创建TreeNode。TreeNode形成一个双向链表,然后再调用TreeNode上的treeify操作,形成红黑树(链表转红黑树)
public void putAll(Map extends K, ? extends V> m)
直接调用putMapEntries
public V remove(Object key)
直接调用removeNode实现删除功能。
final Node
说明:内部实现
实现:根据hash值找到table中的项,然后直接在红黑树或链表中删除节点即可。没有特殊之处(面试也不会问,因为这里没啥好问的)
public void clear()
说明:清空HashMap
实现:table中的每个元素赋值为null,table空间不会重新分配。
public boolean containsValue(Object value)
说明:判断是否包含指定value
实现:第一层循环遍历table访问每个Node,再在第二层循环中遍历每个Node(通过next指针找到下一个Node)。注:红黑树Node也有next指针。
public Set
说明:返回HashMap中的所有key且与HashMap绑定,HashMap中数据变化则这里返回的Set也会跟着变化。支持删除操作(HashMap也会跟着变),不支持新增操作。
实现:直接返回HashMap中的keySet成员,这个keySet由put等其他操作维护。
红黑树1. 什么是红黑树?
红黑树是一种平衡二叉树,它的查找操作是logN的,但是比完全平衡的二叉树慢。它的插入和删除操作比平衡二叉树更快。
2. 红黑树满足哪5条性质:
性质一:节点是红色或者黑色;
性质二:根节点必须是黑色;
性质三:每个叶节点(NIL或空节点)必须是黑色;
性质四:每个红色节点的两个子节点必须都是黑色的;
性质五:从任一节点走到其每个叶子节点的所有路径都包含相同数目的黑色节点;
3. HashMap为什么用红黑树而不用平衡二叉树?
在查询、插入和删除操作中取得一个折中。



