浙江龙网

  1. 首页 > 生活百科 > >

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

生活百科


所谓的「哈希」，就是 Key 通过哈希函数得到一个函数值（哈希值、哈希地址）的过程 。
什么是哈希冲突？在数学上，函数的映射可以是一对一，也可以是多对一的，也就是说一个 $x$ 可以映射一个 $y$ ，也可以多个 $x$ 映射到同一个 $y$ 上 。
哈希函数也一样 ， 它有可能出现多对一的情况，即多个不同的 Key，通过哈希函数得到同一个地址（哈希值） 。
这就出现问题了，这种情况，就称为「哈希冲突」 。

哈希冲突完整定义：哈希函数可能把两个或两个以上的不同关键字映射到同一个地址，这种情况称为冲突 。发生冲突的不同关键字称为同义词 。
你想一下，如果两个不同的 Key，比方说 Key1 和 Key2，通过哈希函数得到同一个地址，那么你不解决这个冲突，直接进行存储 ， 那么就是这样的：
  • Key1 先存储，Key2 后存储，自然只保存了 Key2
  • Key2 先存储，Key1 后存储，自然只保存了 Key1
这种情况是我们不想看到的，所以我们必须解决冲突 。
如何解决冲突？在解决冲突之前 ， 我们应该尽量减少冲突的发生，这就需要设计得OK的哈希函数 。当然冲突是必然的，是逃不掉的，当数据量够多的时候 ， 必然会发生冲突，所以就需要设计好解决冲突的方法 。
哈希函数的设计注意点：
  • 函数的定义域必须包含所有的 Key，函数的值域必须包含所有的 Value 。其中值域是跟哈希表的大小有关的 。
  • 函数计算出来的地址（哈希值）应该能够均匀分布在哈希表的内存地址空间上，从而减少冲突的发生 。
  • 函数能够简单就简单实现 ， 这样计算会很快 。
解决冲突的方法：
解决冲突的思想就是为冲突的 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 null values and the null key. (The HashMap class is roughly equivalent to Hashtable, except that it is unsynchronized and permits nulls.) This class makes no guarantees as to the order of the map; in particular, it does not guarantee that the order will remain constant over time.
哈希表是通过实现 Map 接口实现的，因为 Map 接口提供了所有的映射操作，并且允许空值和空键（HashMap这个类可以简单的看作是 HashTable 类 ， 与之不同是，HashMap 是非同步且允许存储空数据的） 。HashMap 这个类不保证映射的顺序，特别是不保证这个顺序会随着时间的改变而保持不变 。
This implementation provides constant-time performance for the basic operations (get and put), assuming the hash function disperses the elements properly among the buckets. Iteration over collection views requires time proportional to the "capacity" of the HashMap instance (the number of buckets) plus its size (the number of key-value mappings). Thus, it's very important not to set the initial capacity too high (or the load factor too low) if iteration performance is important.
当哈希函数恰当地将元素映射到哈希桶（the buckets）中 ， 那么就具有常量时间里的基本操作（get 和 put）性能 。遍历 HashMap 这个集合的时候，遍历的时间与 HashMap 实例的容量（哈希桶的数量）加上它的大?。↘ey和Value的映射数量，即键值对的数量）成正比，因此，不要设置初始的容量太高，或者负载因子太低，这是非常重要的 。
An instance of

推荐阅读


上一篇：Mysql InnoDB Buffer Pool

下一篇：记录在linux上单机elasticsearch8和kibana8