关于java:Hash与HashMap

3次阅读

共计 1845 个字符，预计需要花费 5 分钟才能阅读完成。

近几日写代码时看到了老师应用缓存去解决一些须要常常从数据库中被查问的货色，而缓存用到了 HashMap，因为考研时学到了 Hash 存储，所以借此再去理解一下 HashMap.

Hash 是将任意长度的数据映射出无限长度的数据，用来代表源数据，小到一串数据，大到任意类型任意大小的文件都能够通过肯定的算法来映射出一串数据，并且雷同的可能性极小，所以 hash 罕用来进行文件完整性校验。
常见的 hash 算法如 MD-5,SHA-1,SHA-256 等。
这些一罕用于明码加密。
咱们拿 java 中的 String.hashCode()函数为例，展现一个 hash 算法的计算过程

public int hashCode() {
    int h = hash; // default 0
    if (h == 0 && value.length > 0) {char val[] = value;

        for (int i = 0; i < value.length; i++) {h = 31 * h + val[i];
        }
        hash = h;
    }
    return h;
}

咱们能够看到，hashCode()函数循环乘加字符串中的每个字符，失去最终的 hash 值。

如果仅仅依据失去的 hash 值来存储则会大大节约存储空间，如 hash 值为 123456789 则存到 123456789 号地位上，hash 值为 987654321 则存到 987654321 地位上，那么会极大节约空间。所以截下来咱们用到 hash 函数进行再次映射。
学过数据结构的同学应该有所理解，hash 存储有一个散列表，所有的数据都寄存在散列表中的相应地位上。散列表长度固定，比方散列表长度为 10，那么表中就有 0,1,2…9 十个地位。咱们所要寄存的数据失去 hash 值通过 hash 函数映射到这 10 个地位中。

为了达到此成果，有很多结构散列值的算法，如除留余数法、平方取中法、折叠法、随机数法、数学分析法等。咱们以最常见的除留余数法，就是把键值通过一个固定的算法函数既所谓的 hash 函数转换成一个整型数字，而后将该数字对散列表长度进行取余，取余后果就当作散列表的下标(散列值)。

不同的 hash 通过算法不免失去雷同的存储地位，为了解决这种碰撞咱们须要进行解决。
解决碰撞的办法有很多种，如线性探测法、拉链法等等。
线性探测法就是如果通过 hash 函数算出的地位上曾经有数据了，那就看紧邻的下一个地位有没有数据，没有数据就放到这个地位上，顺次类推。

如 31 就是应该在 6 的地位上，然而 6 的地位上曾经有 27 了，所以咱们找 7 地位，7 地位没有数据，咱们放到 7 地位上。
负载因子 = 被除数 / 散列表长度
如负载因子为 0.75，被除数为 12，在散列表长度为 16。
拉链法是每个存储地位存储一个指针，每个指针都指向一个链表。将通过 hash 函数算出的雷同地位的数据顺次放到链表上。

hashMap 也是散列表，同时也应用拉链解决抵触。

HashMap 的默认初始容量为 2^4(=16)，即便创立时指定初始容量，HashMap 外部也会计算一个不小于指定容量的、最靠近的且为 2 的整数次幂的一个值作为初始容量。
为什么是 2 的整数次幂？
因为咱们在 hash 存储时应用了除留余数法，然而求余数计算比较复杂。所以咱们简化为与 2^n- 1 进行与操作。从而失去 2 的 n 次方个不同的后果。如果一个数据对应二进制为 11011011，那么它与 1111 的与运算失去后四位 1011。
如果不是 2 的整数倍，比如说容量为 12，那么对应每个 hash 值与 1011（11）进行与运算，那么 10111101 与 1011 与运算为 1001，那么 X1XX 地位上永远不会有数据。
同时也对拉链表进行优化。咱们想一种最坏状况，如果所有数据集中到同一链表中，那么咱们查找起来就像在查找一个程序表一样。
为了解决这个问题，咱们在链表过长时，优化成为红黑数，个别当链表长度超过 8 时，使其变成红黑数，红黑数能够了解为二叉搜寻树的一种。反之当长度小于 6 时，将红黑数变为链表。

hashMap 存储键值对通过 Entry 类，用 Entry 数组存储键值对，Entry 类外面有四个属性：hash、K、V、next，别离存储哈希值、键对象、值对象、下一个 Entry 对象援用。
Entry 源码

Entry 对象结构图

Entry 存储结构图。
通过对 key 对象进行 hashCode(), 获取 hash 值，而后与运算获取存储地位。

ConcurrentHashMap 和 HashMap 思路是差不多的，然而因为它反对并发操作，所以要简单一些。

正文完