哈希表、哈希冲突

本文主要是介绍哈希表、哈希冲突，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

哈希表

在哈希表中进行数据操作时性能很高，不考虑哈希冲突的情况下，仅需一次定位即可完成，时间复杂度为O(1)。

我们知道数据结构的物理存储结构有两种：顺序存储结构和链式存储结构。

而数组是根据下标查找某个元素的，一次定位就可以达到，哈希表利用了这种特性，哈希表的主干就是数组。

比如我们要新增或查找某个元素，我们通过把当前元素的key(关键字) 通过某个函数映射到数组中的某个位置，通过数组下标一次定位就可完成操作。
这个函数可以简单描述为：存储位置 = f(key) ，这个函数f一般称为哈希函数。

添加数据时，如果两个不同的元素，通过哈希函数得出的实际存储地址相同，就会产生哈希冲突，也叫哈希碰撞。也就是要进行新元素插入时，发现对应地址已经被存在其他元素。

因此哈希函数的设计至关重要，好的哈希函数会尽可能地保证计算简单并且散列地址分布均匀，但是，数组是一块连续的固定长度的内存空间，再好的哈希函数也不能保证得到的存储地址绝对不发生冲突。

这篇关于哈希表、哈希冲突的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！