经验总结

  1. 首页 > 生活 > >

浅入浅出 1.7和1.8的 HashMap( 二 )

生活百科


哈希表如何存储数据？哈希表存储数据，给定一个 Key，存储一个 Value 。这里就需要用到一个哈希函数（散列函数） 。
以数学中的「函数」来理解，就是有一个函数是这样的 $f(x) = y$，一个 $x$ 通过函数 $f$ 映射成值 $y$。
那么哈希函数也可以这样理解：$hash(key) = address$
即键通过哈希函数映射成了一个地址，这个地址可以是数组下标、内存地址等 。
所以呢，存储就是，通过哈希函数，把 Key 映射到某个地址，然后将 Value 存储到这个地址上 。
那么存储后如何获取，如何查找到这个 Value 呢？还是一样，通过哈希函数获得 Key 映射的地址，然后从这个地址取出 Value。理想的情况下，在哈希表中查找数据，查找的时间复杂度是 $O(1)$。
所谓的「哈希」，就是 Key 通过哈希函数得到一个函数值（哈希值、哈希地址）的过程 。
什么是哈希冲突？在数学上，函数的映射可以是一对一，也可以是多对一的，也就是说一个 $x$ 可以映射一个 $y$，也可以多个 $x$ 映射到同一个 $y$ 上 。
哈希函数也一样，它有可能出现多对一的情况，即多个不同的 Key，通过哈希函数得到同一个地址（哈希值） 。
这就出现问题了，这种情况，就称为「哈希冲突」 。

哈希冲突完整定义：哈希函数可能把两个或两个以上的不同关键字映射到同一个地址，这种情况称为冲突 。发生冲突的不同关键字称为同义词 。
你想一下，如果两个不同的 Key，比方说 Key1 和 Key2，通过哈希函数得到同一个地址，那么你不解决这个冲突，直接进行存储，那么就是这样的：
  • Key1 先存储，Key2 后存储，自然只保存了 Key2
  • Key2 先存储，Key1 后存储，自然只保存了 Key1
这种情况是我们不想看到的，所以我们必须解决冲突 。
如何解决冲突？在解决冲突之前，我们应该尽量减少冲突的发生，这就需要设计得OK的哈希函数 。当然冲突是必然的，是逃不掉的，当数据量够多的时候，必然会发生冲突，所以就需要设计好解决冲突的方法 。
哈希函数的设计注意点：
  • 函数的定义域必须包含所有的 Key，函数的值域必须包含所有的 Value 。其中值域是跟哈希表的大小有关的 。
  • 函数计算出来的地址（哈希值）应该能够均匀分布在哈希表的内存地址空间上，从而减少冲突的发生 。
  • 函数能够简单就简单实现，这样计算会很快 。
解决冲突的方法：
【浅入浅出 1.7和1.8的 HashMap】解决冲突的思想就是为冲突的 Key 找下一个没有被占用的地址 。
  • 开放定址法
  • 拉链法
这里就只说这个拉链法 。
拉链法把所有发生冲突的 Key 存储在一个线性链表中，这个链表由 Key 哈希过后得到的地址（哈希地址）唯一标识，这就是拉链法，适用于经常插入和删除的情况 。
哈希表查找效率平均查找长度（ASL-Average Search Length），可衡量哈希表的查找效率 。
ASL依赖于哈希表的「装填因子（负载因子）」$$装填因子的定义：α = \frac{哈希表中的元素个数}{哈希表的长度}?$$装填因子越大，那么冲突的可能就越大，反之亦然 。
1.7 版 HashMap
浅入浅出 1.7和1.8的 HashMap

文章插图
现在知道什么是哈希表了，那么接下来就看看 Java 中对哈希表的实现——HashMap
再次初识 1.7 的 HashMap我们先看看文档是怎样说的，同时我进行了大体的翻译 。（这些说明可以从源码的开头找到）
Hash table based implementation of the Map interface. This implementation provides all of the optional map operations, and permits

经验总结扩展阅读


上一篇：干红菇浸泡时间多长为宜

下一篇：2023年9月23日是坐船的黄道吉日吗 2023年9月23日适合坐船吗