07哈希表【散列表】

数据结构(九)之哈希表理论

如需转载, 请咨询作者, 并且注明出处.有任何问题, 可以关注我的微博: coderwhy, 或者添加我的微信: 372623326 哈希表是一种非常重要的数据结构, 很多学...

https://www.jianshu.com/p/6e88d63061f2

一、理论知识

哈希表介绍

• 哈希表是一种非常重要的数据结构, 几乎所有的编程语言都有直接或者间接的应用这种数据结构.

• 哈希表通常是基于数组进行实现的, 但是相对于数组, 它也很多的优势:
• 它可以提供非常快速的插入-删除-查找操作
• 无论多少数据, 插入和删除值需要接近常量的时间: 即O(1)的时间级. 实际上, 只需要几个机器指令即可
• 哈希表的速度比树还要快, 基本可以瞬间查找到想要的元素
• 哈希表相对于树来说编码要容易很多.

• 哈希表相对于数组的一些不足:
• 哈希表中的数据是没有顺序的, 所以不能以一种固定的方式(比如从小到大)来遍历其中的元素.
• 通常情况下, 哈希表中的key是不允许重复的, 不能放置相同的key, 用于保存不同的元素.

• 那么, 哈希表到底是什么呢?
• 似乎还是没有说它到底是什么.
• 这也是哈希表不好理解的地方, 不像数组和链表, 甚至是树一样直接画出你就知道它的结构, 甚至是原理了.
• 它的结构就是数组, 但是它神奇的地方在于对下标值的一种变换, 这种变换我们可以称之为哈希函数, 通过哈希函数可以获取到HashCode.
• 不着急, 我们慢慢来认识它到底是什么.

二、为什么使用质数