乐趣区

关于hashmap:HashMap底层原理

一、存储构造

HashMap 是数据结构散列表在 Java 中的实现版本,通过对键值进行哈希函数计算出键值对在散列表中的下标地位,能够快速访问到相应数据,工夫复杂度为 O(1)。

但因散列表数组长度无限,不同键值通过哈希函数计算出的下标地位可能统一,引发哈希抵触,为了解决这个问题,通常将哈希抵触的数据组成一个链表挂到散列表桶节点上,jdk7 及以前版本都是如此解决,工夫复杂度为 O(n),构造如下图:

jdk8 中对链表构造做了优化,在肯定条件下将链表转为红黑树,晋升查问效率。红黑树是一种二叉均衡树,工夫复杂度为 O(logn),构造如下图:

二、存取原理

put() 办法
  1. 调用哈希函数 hash(key) 计算出键值 key 的哈希值 hash,再用此哈希值 hash 和散列表长度 -1 做与运算失去数组下标;
  2. 依据数组下标找到指标 bucket,如果 bucket 上没有任何元素,就依据键值对创立一个新节点 Node,赋值给该 bucket 上;
  3. 如果以后 bucket 上有链表,且头结点就匹配(哈希值 hash 相等,key 值雷同或 equals 相等),那么就将头结点上的值 value 替换;
  4. 若第 2、3 步不满足,以后 bucket 上的头结点是树结构结点类型 TreeNode,则转为红黑树的插入操作;
  5. 若第 2、3、4 步都不满足,则对链表做遍历操作;

    ​ 1)若链表中有节点匹配,则做 value 替换;

    ​ 2)若没有结点匹配,则在链表开端追加;(jdk7 应用头插法,jdk8 应用尾插法)

    ​ 3)查看链表长度是否超过 TREEIFY_THRESHOLD(默认大小为 8),若超过则执行红黑树转换操作;

  6. 以上操作执行完之后,再查看以后键值对的数量比例是否超过了负载因子,若超出,则进行扩容。
get() 办法
  1. 依据 key 计算出 hash 值,进一步计算失去哈希表的指标下标 index;
  2. 若指标 bucket 头结点匹配,就返回头结点的 value;
  3. 若指标 bucket 上为红黑树,则在红黑树上查找;若不是红黑树,遍历链表;
  4. 若都没匹配到,返回 null;

三、扩容

个别状况下,当键值对数量比例超过负载因子便会触发扩容。每次扩容后的容量都是之前容量的 2 倍。

四、线程不平安

退出移动版