侧边栏壁纸
博主头像
小吴同学博主等级

去学习,去读书,去受教育,去看山川河流,去远方!!!

  • 累计撰写 15 篇文章
  • 累计创建 9 个标签
  • 累计收到 2 条评论

目 录CONTENT

文章目录

hashMap简单学习

小吴同学
2022-10-20 / 0 评论 / 13 点赞 / 311 阅读 / 1,587 字

#Hash概念

Hash也称散列、哈希,基本原理就是把任意长度的输入,通过Hash算法变成固定长度的输出.这个映射规则就是对应的Hash算法,而原始数据映射后的二进制串就是哈希值.

#Hash特点

1.从Hash值不可以反向推导出原始数据

2.输入数据的微小变化会得到不同的Hash值,相同数据得到的相同的值

3.哈希算法的执行效率要高,长的文本也能快速地计算出哈希值

4.Hash算法的冲突概率要小

由于Hash的原理是将输入空间的值映射成Hash空间内,而Hash值的空间远小于输入的空间,根据抽屉原理,一定会存在不同的输入被映射成相同输出的结果

#Hash继承体系

HashMap继承了AbstractMap,而AbstractMap实现了Map接口

#Node结构

final int hash;

final K key;

V value;

Node<K,V> next;

这里的hash不是key的哈希值,看源码

static final int hash(Object key) {

int h;

return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); #是为了让高16位也参与路由运算

}

#路由寻址地址

i = (n - 1) & hash

#让高16位参与运算的原因

当数组的长度很短时,只有低位数的hashcode值能够参与运算,而让高16位参与运算可以更好的均匀散列,减少碰撞,进一步降低hash冲突的几率

#底层数据结构

JDK1.7前是数组+链表

JDK1.8后是数组+链表+红黑树

#HashMap为什么引入红黑树

以空间换时间,链表的查询效率是o(n),而红黑树是o(logn)

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16#默认初始容量

static final int MAXIMUM_CAPACITY = 1 << 30;#最大长度

static final float DEFAULT_LOAD_FACTOR = 0.75f;#负载因子

#树化阈值

static final int TREEIFY_THRESHOLD = 8;

static final int MIN_TREEIFY_CAPACITY = 64;

static final int UNTREEIFY_THRESHOLD = 6;#树降级为链表

transient Node<K,V>[] table;#哈希表

transient int size;#容量

transient int modCount;#修改次数

int threshold;#扩容阈值

final float loadFactor;#负载因子

#构造方法中这个的作用是返回大于等于cap的2的次方数

static final int tableSizeFor(int cap) {

int n = cap - 1;

n |= n >>> 1;

n |= n >>> 2;

n |= n >>> 4;

n |= n >>> 8;

n |= n >>> 16;

return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;

}

当没有插入元素时容量和阈值是一样的,当插入一个元素过后阈值会重新计算 = 容量 * 负载因子

可以使用这段代码查看

public static void main(String[] args) throws Exception {

//指定初始容量15来创建一个HashMap

HashMap m = new HashMap(15);

//获取HashMap整个类

Class<?> mapType = m.getClass();

//获取指定属性,也可以调用getDeclaredFields()方法获取属性数组

Field threshold = mapType.getDeclaredField(“threshold”);

//将目标属性设置为可以访问

threshold.setAccessible(true);

//获取指定方法,因为HashMap没有容量这个属性,但是capacity方法会返回容量值

Method capacity = mapType.getDeclaredMethod(“capacity”);

//设置目标方法为可访问

capacity.setAccessible(true);

//打印刚初始化的HashMap的容量、阈值和元素数量

System.out.println(“容量:”+capacity.invoke(m)+" 阈值:“+threshold.get(m)+” 元素数量:"+m.size());

for (int i = 0;i<17;i++){

m.put(i,i);

 //动态监测HashMap的容量、阈值和元素数量

System.out.println(“容量:”+capacity.invoke(m)+" 阈值:“+threshold.get(m)+” 元素数量:"+m.size());

}

}

#put操作

1.如果最开始没有那么会在这里初始化table

put操作四种情况

1.桶位为空 => 直接插入

2.桶位不为空没有链化 => 比较key是否相同,相同就替换,否则形成node结点形成链表

3.已经链化 => 与2类似,但是加入过后是否达到树化阈值

4.红黑树 => 还没看红黑树

#resize方法中的扩容

Node<K,V>[] oldTab = table;

#oldCap,oldThr就是老的容量和扩容阈值

int oldCap = (oldTab == null) ? 0 : oldTab.length;

int oldThr = threshold;

#newCap,newThr就是新的容量和扩容阈值

int newCap, newThr = 0;

#正常扩容(已经初始化过)

if (oldCap > 0) {

#当老容量大等于最大的时候就不扩容,就将扩容阈值变成Integer.MAX_VALUE(几乎不发生)

  if (oldCap >= MAXIMUM_CAPACITY) {

   threshold = Integer.MAX_VALUE;

   return oldTab;

 }

  #扩大一倍容量,但是阈值是否扩大一倍必须满足老容量大等于16

  else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&

      oldCap >= DEFAULT_INITIAL_CAPACITY)

   newThr = oldThr << 1; // double threshold

}

#初始化

else if (oldThr > 0) // initial capacity was placed in threshold

 newCap = oldThr;

#初始化

else {       // zero initial threshold signifies using defaults

 newCap = DEFAULT_INITIAL_CAPACITY;

 newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);

}

if (newThr == 0) {

 float ft = (float)newCap * loadFactor;

 newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?

      (int)ft : Integer.MAX_VALUE);

}

threshold = newThr;

#resize方法中的复制

Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];

table = newTab;

#说明本次扩容前,table不为null

if (oldTab != null) {

  for (int j = 0; j < oldCap; ++j) {

   Node<K,V> e;

    #e就是当前节点

    #说明当前桶位中有数据但不知到是 单个数据还是链表还是红黑树

    if ((e = oldTab[j]) != null) {

    #方便JVM GC时的垃圾回收

     oldTab[j] = null;

      #第一种情况,当前桶位只有一个元素,没有发生碰撞,直接计算出当前元素应放的位置

      if (e.next == null)

       newTab[e.hash & (newCap - 1)] = e;

      #树化  

      else if (e instanceof TreeNode)

       ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);

      else { // preserve order

       #链表

       

        #低位链表:存放在扩容之后的数组的下标位置,与当前数组的下标位置一致

       Node<K,V> loHead = null, loTail = null;

       #高位链表:存放在扩容之后的数组的下标位置,当前数组的下标位置+扩容前数组的长度

       Node<K,V> hiHead = null, hiTail = null;

       Node<K,V> next;

        do {

         next = e.next;

          #证明这是一个低位

          if ((e.hash & oldCap) == 0) {

            if (loTail == null)

             loHead = e;

            else

             loTail.next = e;

           loTail = e;

         }

          #高位

          else {

            if (hiTail == null)

             hiHead = e;

            else

             hiTail.next = e;

           hiTail = e;

         }

       } while ((e = next) != null);

        #将高位和低位链的头部给数组位置节点

        if (loTail != null) {

         loTail.next = null;

         newTab[j] = loHead;

       }

        if (hiTail != null) {

         hiTail.next = null;

         newTab[j + oldCap] = hiHead;

       }

     }

   }

 }

}

13

评论区