HashMap原理

HashMap底层原理

HashMap底层原理

​ JDK1.8 之前 HashMap 底层是 数组和链表 结合在一起使用也就是 链表散列。

​ HashMap 通过 key 的 hashCode 经****过扰动函数处理过后得到 hash 值，然后通过 (n - 1) & hash 判断当前元素存放的位置（这里的 n *指的是数组的***长度）；

​ 所谓扰动函数指的就是 HashMap 的 hash 方法。使用 hash 方法也就是扰动函数是为了防止一些实现比较差的****hashCode() 方法 换句话说使用扰动函数之后可以减少碰撞。

JDK 1.8 HashMap 的 hash 方法源码：

static final int hash(Object key) { 
    int h;
    // key.hashCode()：返回散列值也就是hashcode 
    // ^ ：按位异或 
    // >>>:无符号右移，忽略符号位，空位都以0补齐 
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }

/*** Returns a power of two size for the given target capacity. */ 
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; }

小总结：hashMap在确定元素位置时，先调用 hashcode()算出一个值，然后再和它本身 右移16位得到的 值进行 异或运算 返回一个hash值，最后用这个值和数组长度减一进行与运算确定元素位置；

补充：

1. ArrayList 的扩容机制：

   三个构造器：

   • 无参构造器，返回一个默认大小为10的容器
   • 一个参数构造器，返回指定大小的数组
   • 还有一个是将collection转换成arraylst，再将值复制一份；

2. int newCapacity = oldCapacity + (oldCapacity>> 1); 是最重要的一条语句，oldCapacity 为原来的容量，oldCapacity >> 1 表示向右移一位，相当于除以 2，即 newCapacity 是原来容量的 1.5 倍。如果扩大 1.5 倍后还不够，则直接将其扩大至 minCapacity 大小。判断 newCapacity 是否 超过了最大容量 MAX_ARRAY_SIZE ，

3. 将原来数据复制到扩容后的数组中。elementData [size++] = e; 将新加入元素添加至数组中。（费空间时间）

Others：

• 如果数组长度变化，hashmap的索引值也会变化
• 🙇