• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

数据结构:哈希表

互联网 diligentman 2周前 (04-29) 10次浏览

目录

  • 第一章 哈希表介绍
  • 第二章 哈希冲突
  • 第三章 哈希函数
  • 第四章 哈希表实现

项目地址:https://gitee.com/caochenlei/data-structures

第一章 哈希表介绍

设计一个写字楼通讯录,存放该写字楼所有公司的通讯信息,座机号码作为 key(假设座机号码最长是 8 位),公司详情(名称、地址等)作为 value,要求添加、删除、搜索的时间复杂度要求是 O(1),实现代码如下:

数据结构:哈希表

我们发现上述代码可以实现要求,但是空间复杂度极大,空间利用率极低,非常浪费内存空间,其实数组 companies 就是一个哈希表。

哈希表(Hash Table,也叫散列表),是根据关键码值(Key Value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做 哈希函数(散列函数) ,存放记录的数组叫做 哈希表(散列表)

数据结构:哈希表

第二章 哈希冲突

哈希冲突(Hash Collision,也叫哈希碰撞),简单的来说就是:2 个不同的 key,经过哈希函数计算出相同的结果。

数据结构:哈希表

解决哈希冲突有很多种方法,我们这里重点介绍链地址法(Separate Chaining),简单的来说就是:通过链表将同一index元素串起来。

数据结构:哈希表

第三章 哈希函数

哈希函数指将哈希表中元素的关键键值映射为元素存储位置的函数。

哈希表中哈希函数的实现步骤,大概如下:

  • 先生成 key 的哈希值(必须是整数)。
  • 再让 key 的哈希值跟数组的大小进行相关运算,生成一个索引值。

数据结构:哈希表

为了提高效率,可以使用 & 位运算取代 % 运算,但是这是有前提的,那就是必须将数组的长度设计为 2 的幂(2n)。

数据结构:哈希表

良好的哈希函数,可以让哈希值更加均匀分布,减少哈希冲突次数,提升哈希表的性能。

那么问题又来了,对于 key 来说,可能是不同的数据类型,那如何计算他的哈希值呢?

key 的常见种类可能有:整数、浮点数、字符串、自定义对象。不同种类的 key,哈希值的生成方式不一样,但目标是一致的,尽量让每个 key 的哈希值是唯一的,尽量让 key 的所有信息参与运算,并且最终生成的哈希值必须是一个整数。

Integer整数: 整数值当做哈希值,比如 10 的哈希值就是 10

数据结构:哈希表

Float浮点数: 将存储的二进制格式转为整数值

数据结构:哈希表

Long整数、Double浮点数:

数据结构:哈希表

这个 >>> 和 ^ 的作用是什么?

由于Long和Double的底层二进制位数远远超过了Integer的32位,为了满足尽量让 key 的所有信息参与运算,所以通过 >>> 右移,让当前值的高32位和低32位进行运算,混合计算出32位的整数哈希值,最终计算出来的数值高32无意义,舍去即可。这里给出一个案例:

数据结构:哈希表

字符串:

我们首先来思考一个问题,整数 5489 是如何计算出来的?

5489 = 5 ∗ 103 + 4 ∗ 102 + 8 ∗ 101 + 9 ∗ 100

而我们的字符串是由若干个字符组成的,比如字符串 jack,由 j、a、c、k 四个字符组成,字符的本质就是一个整数。

因此,jack 的哈希值可以表示为 j ∗ n3 + a ∗ n2 + c ∗ n1 + k ∗ n0,等价于 [ ( j ∗ n + a ) ∗ n + c ] ∗ n + k

在JDK中,乘数 n 为 31,为什么用 31?

由于 31 不仅仅是符合2n – 1,它还是个奇素数(既是奇数,又是素数,也就是质数),素数和其他数相乘的结果比其他方式更容易产成唯一性,减少哈希冲突,有那么多素数,那为啥是31呢,是经过观测分布结果后的选择,并且JVM会将 31 * i 优化(i << 5) – i

数据结构:哈希表

自定义对象:

自定义对象需要实现 equals 和 hashCode 方法,以下示例代码的 equals 和 hashCode 方法由 idea 自动生成。

注意:这里实现 equals 方法和生成 hashCode 并没有直接联系,仅仅是为了后边写代码方便,也就一块生成了。

数据结构:哈希表

这里给出 Objects.hash(...) 的底层实现:

数据结构:哈希表

数据结构:哈希表

第四章 哈希表实现

【实现代码】

public class HashTable<Key, Value> {
    private int M;                              //哈希表的大小
    private int N;                              //键值对的对数
    private SymbolTable<Key, Value>[] table;    //存放链表对象的数组,这里采用无序符号表,也可以用红黑树

    public HashTable(int M) {
        this.M = M;
        table = new SymbolTable[M];
        for (int i = 0; i < M; i++) {
            table[i] = new SymbolTable<>();
        }
    }

    //获取哈希表键值个数
    public int size() {
        return N;
    }

    //判断哈希表是否为空
    public boolean isEmpty() {
        return N == 0;
    }

    //获取指定key哈希值
    private int hash(Key key) {
        return key.hashCode() & (table.length - 1);
    }

    //向哈希表中添加键值
    public void put(Key key, Value value) {
        table[hash(key)].put(key, value);
        N++;
    }

    //删除哈希表中的key
    public void delete(Key key) {
        table[hash(key)].delete(key);
        N--;
    }

    //获取key对应的value
    public Value get(Key key) {
        return table[hash(key)].get(key);
    }

    //获取哈希表中所有key的集合
    public Set<Key> keySet() {
        Set<Key> keySet = new HashSet<>();
        for (SymbolTable<Key, Value> keyValueSymbolTable : table) {
            keySet.addAll(keyValueSymbolTable.keySet());
        }
        return keySet;
    }

    //获取哈希表中所有value的集合
    public Set<Value> valueSet() {
        Set<Value> valueSet = new HashSet<>();
        for (SymbolTable<Key, Value> keyValueSymbolTable : table) {
            valueSet.addAll(keyValueSymbolTable.valueSet());
        }
        return valueSet;
    }
}

【测试代码】

public class HashTableTest {
    public static void main(String[] args) {
        HashTable<Integer, String> hashTable = new HashTable<>(16);

        hashTable.put(1, "刘备");
        hashTable.put(2, "张飞");
        hashTable.put(3, "关羽");
        hashTable.put(4, "赵云");
        hashTable.put(5, "曹操");
        hashTable.put(6, "吕布");

        System.out.println(hashTable.size());
        System.out.println(hashTable.isEmpty());
        System.out.println(hashTable.keySet());
        System.out.println(hashTable.valueSet());
        for (Integer key : hashTable.keySet()) {
            System.out.println(key + ":" + hashTable.get(key));
        }
        for (Integer key : hashTable.keySet()) {
            hashTable.delete(key);
        }
        System.out.println(hashTable.size());
        System.out.println(hashTable.isEmpty());
        System.out.println(hashTable.keySet());
        System.out.println(hashTable.valueSet());
    }
}

【运行效果】

6
false
[1, 2, 3, 4, 5, 6]
[关羽, 张飞, 吕布, 刘备, 曹操, 赵云]
1:刘备
2:张飞
3:关羽
4:赵云
5:曹操
6:吕布
0
true
[]
[]


程序员灯塔
转载请注明原文链接:数据结构:哈希表
喜欢 (0)