数据结构3、散列表 Hash table

2021-12-19 本文已影响0人四月不见

散列表（哈希表）同时又被称为散列映射、映射、字典和关联数组，是一种通过将键（key）映射为值（value）从而实现快速查找的数据结构。
数组和链表都被直接映射到内存，但散列表更复杂，它使用散列函数来确定元素存储的位置。散列表也使用数组来存储数据，由键和值组成。

本章将介绍一种简单、常见的实现方式。

我们使用一个链表构成的数组与一个散列函数来实现散列表。当插入键和值时，我们按照如下方法操作：

首先，计算键的散列值。
键的散列值通常为int或long型。注意，不同的两个键可以有相同的两个散列值，因为键是无穷的，而int型的总数是有限的。
之后，将散列值映射为数组的索引。
可以使用类似于hash(key)%array_lenght的方式完成这一步骤，不同的两个散列值则有可能被映射到相同的数
组索引。
此数组索引处存储的元素是一系列由键和值为元素组成的链表。
请将映射到此索引的键和值存储到这里。由于存在冲突，我们必须使用链表：有可能对于相同的散列值有不同的键，也有可能不同的散列值被映射到了同一索引。

通过键来获取值则需重复此过程。首先通过键计算散列值，再通过散列值计算索引。之后查找链表来获取该键所对应的值。

如果冲突发生很多次，最坏情况下的时间复杂度是O(N)，其中N是键的数量。但是我们通常假设一个不错的实现方式会将冲突数量保持在最低水平，在此情况下，时间复杂度是O(1)。

另一种方法是可以通过平衡二叉搜索树来实现散列表，该方法的查找时间是O(logN)。该方法的好处是用到的空间可能更少，因为我们不需要分配一个大数组，还可以按键的顺序进行迭代访问，在某些时候这样做很有用。