hashmap中的一些小点（个人总结）

capacity <<= 1：

            int i  = 1;

          //类似于 i++就是 i = i+1;的这结构
          //i = i<<1  i等于i乘以2的1次方
          //i <<= 1;
          //i = i<<2  i等于i乘以2的2次方,>>就是相除了
          i <<= 2;
          System.out.println("结果是：" + i);

java中有三种移位运算符：

// <<：左移运算符，num << 1,相当于num乘以2
// >>：右移运算符，num >> 1,相当于num除以2
// >>>：无符号右移，忽略符号位，空位都以0补齐
无符号右移的规则只记住一点：忽略了符号位扩展，0补最高位无符号右移运算符>>> 只是对32位和64位的值有意义

            //保证hashCode 不同的算法
            //int 是4位byte的 4*8=32bit ，注意-->12+20=32
           //h>>>20是无符号右移运算，就是将int类型的h的二进制数字位往右移动，左边移出来的空位补上0。
           //即为h = h ^ ((h >>> 20) ^ (h >>> 12));按位异或运算，仅当两个对应的二进制位不相同时，结果为1；否则结果为0。
          static int hash(int h) {
             h ^= (h >>> 20) ^ (h >>> 12);
             return h ^ (h >>> 7) ^ (h >>> 4);
         }

什么是哈希冲突：

哈希计算就是努力的把比较大的数据存放到相对较小的空间中。最常见的哈希算法是取模法。

取模法：数组的长度是5。这时有一个数据是6。那么如何把这个6存放到长度只有5的数组中呢。按照取模法，计算6％5，结果是1，那么就把6放到数组下标是1的位置。那么，7就应该放到2这个位置。到此位置，冲突还没有出现。这时，有个数据是11，按照取模法，11％5＝1，也等于1。那么原来数组下标是1的地方已经有数了，是6。这时又计算出1这个位置，那么数组1这个位置，就必须储存两个数了。这时，就叫哈希冲突。冲突之后就要按照顺序来存放了。

如果数据的分布比较广泛，而且储存数据的数组长度比较大。那么哈希冲突就比较少。否则冲突是很高的。

HashMap就是一个散列表，它是通过“拉链法”解决哈希冲突的

什么是拉链法：

拉链法又叫链地址法，拉链法就是把具有相同散列地址的关键字(同义词)值放在同一个单链表中，称为同义词链表。有m个散列地址就有m个链表，同时用指针数组T[0..m-1]存放各个链表的头指针，凡是散列地址为i的记录都以结点方式插入到以T[i]为指针的单链表中。T中各分量的初值应为空指针.

简单来说拉链法就是数组加链表。

大方向上，HashMap 里面是一个数组，然后数组中每个元素是一个单向链表。
下图中，每个绿色的实体是嵌套类 Entry 的实例，Entry 包含四个属性：key, value, hash 值和用于单向链表的 next。

这个仅仅是示意图，因为没有考虑到数组要扩容的情况

从HashMap的实现来看，我们总结拉链法的实现步骤如下：
1. 计算 key 的 hashValue
2. 根据 hashValue 值定位到 table[hashIndex] 。( table[hashIndex] 是一条链表Node)
3. 若 table[hashValue] 为空则直接插入，不然则添加到链表末尾

最后编辑于：2018.12.19 11:22:47