哈希表的工作原理是怎样的？

本文共计1192个文字，预计阅读时间需要5分钟。

哈希表原理简介 + 哈希表是一种基于关键字key访问值value的数据结构。+ 基本原理 + 哈希表的本质是数组+哈希函数+哈希函数。+ 数组容易理解，那么什么是哈希函数？+ 在哈希表中

哈希表的原理 简介

哈希表是一种根据关键字key来访问值value的一种数据结构。

哈希表的基本原理

哈希表的本质是数组加哈希函数。数组不难理解，那什么是哈希函数？

在哈希表中，它的作用就是将哈希表的某个key作为输入，然后经过一系列的运算后，得到数组的某

个索引。一种很朴素的思路是，先用key计算出一个很大的数，然后对数组长度取模，从而得到索引，这只是众多方法中的一种，其他的比如：直接寻址法，平方取中法等。

得到索引后就可以通过索引对数组执行插入或查找的操作，因为本质上是通过索引来访问数组，所以哈希表的插入和查找的效率非常高，时间复杂度都是O(1)。

哈希冲突

我们不难发现哈希函数是整个哈希表的关键。所以为了更好的性能，我们希望在尽可能短的时间内，相同的key经过哈希函数的计算，可以得到相同的索引，不同的key经过哈希函数的计算，可以得到不同的索引，但在实际中往往事与愿违，不同的key小概率会计算出相同的索引，这就是哈希冲突（collision），几乎所有的哈希函数都存在这个问题。