Arth_u_r的博客

是一种常用的算法技巧，通常用于等线性结构的问题中。它的核心思想是，从而高效地解决问题。

哈希表就是在关键字和存储位置之间建立对应关系，使得元素的查找可以以O(1)的效率进行， 其中关键字和存储位置之间是通过散列函数建立关系。常见的散列函数有如下几种：线性地址法、除数取余法、平方取中法等等。而往往这些方法会遇到一些地址冲突的情况，因此还有解决地址冲突的方法。一种思路是开放地址法，将发生冲突的元素映射到其他地址中，这种思路对应的方法有：线性探测法、平方探测法、再散列法等等；另一种思路是思考能否将地址冲突的元素还是就地存储，不映射到其他地址中，这种思路对应的方法有：拉链法。