散列表 -hashTable

关注

发布于: 2021 年 03 月 14 日

HashTable 解决什么问题

我们先来看一个场景，此场景引自《极客时间的数据结构与算法之美》

假如我们有 89 名选手参加学校运动会。为了方便记录成绩，每个选手胸前都会贴上自己的参赛号码。这 89 名选手的编号依次是 1 到 89。现在我们希望编程实现这样一个功能，通过编号快速找到对应的选手信息。你会怎么做呢？我们可以把这 89 名选手的信息放在数组里。编号为 1 的选手，我们放到数组中下标为 1 的位置；编号为 2 的选手，我们放到数组中下标为 2 的位置。以此类推，编号为 k 的选手放到数组中下标为 k 的位置。因为参赛编号跟数组下标一一对应，当我们需要查询参赛编号为 x 的选手的时候，我们只需要将下标为 x 的数组元素取出来就可以了，时间复杂度就是 O(1)。这样按照编号查找选手信息，效率是不是很高？

假设校长说，参赛编号不能设置得这么简单，要加上年级、班级这些更详细的信息，所以我们把编号的规则稍微修改了一下，用 6 位数字来表示。比如 051167，其中，前两位 05 表示年级，中间两位 11 表示班级，最后两位还是原来的编号 1 到 89。这个时候我们该如何存储选手信息，才能够支持通过编号来快速查找选手信息呢？思路还是跟前面类似。尽管我们不能直接把编号作为数组下标，但我们可以截取参赛编号的后两位作为数组下标，来存取选手信息数据。当通过参赛编号查询选手信息的时候，我们用同样的方法，取参赛编号的后两位，作为数组下标，来读取数组中的数据。

这就是典型的散列思想。其中，参赛选手的编号我们叫做键（key）或者关键字。我们用它来标识一个选手。我们把参赛编号转化为数组下标的映射方法就叫作散列函数（或“Hash 函数”“哈希函数”），而散列函数计算得到的值就叫作散列值（或“Hash 值”“哈希值”）

摘自：https://time.geekbang.org/column/article/64233

从上述的描述的场景中，我们可以得出，hashTable 就是，散列函数+数组的应用。把原本 O(n)的时间复杂度的访问，降到为 O(1)。

散列函数的定义：

就是有一个入参 X，经过散列函数的计算会得出一个非负整数 Y，同时还满足，

如果 key1 = key2，那 hash(key1) == hash(key2)；

如果 key1 ≠ key2，那 hash(key1) ≠ hash(key2)。

java 中 Object 对象的 hashCode 的实现算法是怎样的

在 java 中 Object 对象调用 native 的方法获取对象的 hashCode 的，如下：

public native int hashCode();

jvm 的实现代码

代码

static inline intptr_t get_next_hash(Thread * Self, oop obj) {  intptr_t value = 0 ;  if (hashCode == 0) {     // This form uses an unguarded global Park-Miller RNG,     // so it's possible for two threads to race and generate the same RNG.     // On MP system we'll have lots of RW access to a global, so the     // mechanism induces lots of coherency traffic.     value = os::random() ;  } else  if (hashCode == 1) {     // This variation has the property of being stable (idempotent)     // between STW operations.  This can be useful in some of the 1-0     // synchronization schemes.     intptr_t addrBits = intptr_t(obj) >> 3 ;     value = addrBits ^ (addrBits >> 5) ^ GVars.stwRandom ;  } else  if (hashCode == 2) {     value = 1 ;            // for sensitivity testing  } else  if (hashCode == 3) {     value = ++GVars.hcSequence ;  } else  if (hashCode == 4) {     value = intptr_t(obj) ;  } else {     // Marsaglia's xor-shift scheme with thread-specific state     // This is probably the best overall implementation -- we'll     // likely make this the default in future releases.     unsigned t = Self->_hashStateX ;     t ^= (t << 11) ;     Self->_hashStateX = Self->_hashStateY ;     Self->_hashStateY = Self->_hashStateZ ;     Self->_hashStateZ = Self->_hashStateW ;     unsigned v = Self->_hashStateW ;     v = (v ^ (v >> 19)) ^ (t ^ (t >> 8)) ;     Self->_hashStateW = v ;     value = v ;  }

复制代码

大致思路：

0 == Lehmer random number generator,

1 == "somehow" based on memory address

2 == always 1

3 == increment counter

4 == memory based again("somehow")

5 == read below

随机数
基于内存地址生成
固定值：1，用来测试
自增
利用位移生成随机数

这个 5 个选项是可以通过 jvm 参数来设置的。默认的设置是 5

查看方式：打印所有系统参数 java -XX:+PrintFlagsFinal

5 的话使用的是 XOR-Shift algorithm 算法生成。这个算法是伪随机数生成的算法。具体算法介绍可以查看

https://en.wikipedia.org/wiki/Xorshift

可以加个过滤 java -XX:+PrintFlagsFinal | grep hashCode

那么假设参数设置为跟内存相关，那经过一次 gc 之后，一个对象的内存地址变化了，他的 hashCode 是否会变化？这个是不会的，如果跟内存有关，那也绝不是那地址作为 hash 的唯一因素。一个对象的 hashCode 生成后，整个生命周期都是不会改变的。这个 hashCode 会存在对象头的 identify_hashcode 字段里