1回答

liuyubobobo

2017-10-27

已采纳

哈希表的具体实现原理我在我的三门算法课程中均没有涉及。简单地说，哈希表就是一个数组，通过键值直接索引内存找到相应的值。我们在上一章最后解决的问题使用freq数组，就是一个哈希表。对于每一个字母，我们可以直接找到和这个字母对应的索引（'a'对应0，'b'对应1，...，'z'对应25），进而直接找到这个索引对应的值。

上面的例子，键（字母）和索引的对应关系是简单的。但是在实际情况中，我们的键不一定是字符这么容易可以对应到一个索引的，最典型的情况是字符串。所以，我们需要一个函数，将一个键对应于一个索引，也就是一个整数。这个函数通常就叫做哈希函数。对于不同的键值，有不同的哈希函数的设计方案。同时，哈希函数的设计也有一定的通用方案。感兴趣可以查阅更多资料，一般数据结构的教科书都会具体介绍哈希表和哈希函数。

但即使这样，也避免不了同一个键值通过哈希函数转换成的索引是一样的情况。这种情况叫做“冲突”。一个好的哈希函数就是要大概率的避免冲突。至于冲突的解决方案，也有很多种，最简单地解决方案就是对于同一个索引，存放一个链表，进行顺次查询。

最后，值得一提的是，哈希函数的时间复杂度问题。一个哈希表如果有M个空间，我们有N个key，如果N > M的话，哈希表查找的最好时间复杂度是O(N/M)的。但通常情况下，在实现一个哈希表的时候，当key的数量达到一定程度，比如达到哈希表容量的75%的时候，冲突会大概率发生，此时我们需要为哈希表自动扩容（原理和我们这个课程第二章讲解动态数组的扩容方案差不多）。这个75%通常称为负载率。使用这种手段，我们保证哈希表查找的平均复杂度是O(1)的。当然，是在内存空间足够的情况下：）

哈希表示一个蛮复杂的话题，我不太可能在这么一个回帖里讲清楚。关于哈希表的更多内容，如果感兴趣的话，可以在互联网搜索更多资料。如果我的算法与数据结构课程出进阶版本的话，一定会涉及哈希表的：）

加油！

1

1

ATWJSW

非常感谢！

2017-10-27

共1条回复