哈希表是什么数据结构（什么是哈希表它们与字典的关系是什么）

本文目录

• 什么是哈希表它们与字典的关系是什么
• hash表原理
• 什么是哈希表特点是什么
• 在哈希表、arraylist、数组、堆栈四个中哪个不是数据结构
• 如何画出对应哈希表的数据结构
• 数据结构问题：哈希表的存储结构是什么
• 哈希表—什么是哈希表
• 理解哈希表
• 哈希表概念以及哈希冲突的处理
• 数据结构-Hash

什么是哈希表它们与字典的关系是什么

序列类型用有序的数字键做索引将数据以数组的形式存储。一般索引值与所存储的数据毫无关系。还可以用另一种方式来存储数据:基于某种相关值，比如说一个字符串。我们在日常生活中一直这么做。把人们的电话号码按照他们的姓记录在电话簿上，按照时间在日历或约会薄上添加事件，等等。在这些例子中，你的键就是和数据项相关的值。哈希表是一种数据结构:它按照我们所要求的去工作。哈希表中存储的每一条数据，叫做一个值(value)，是根据与它相关的一个被称作为键(key)的数据项进行存储的。键和值合在一起被称为“键-值对”(key-value pairs)。哈希表的算法是获取键，对键执行一个叫做哈希函数的操作，并根据计算的结果，选择在数据结构的某个地址中来存储你的值。任何一个值存储的地址皆取决于它的键。正因为这种随意性，哈希表中的值是没有顺序的。你拥有的是一个无序的数据集。你所能获得的有序集合只能是字典中的键的集合或者值的集合。方法Keys()或values()返回一个列表，该列表是可排序的。你还可以用items()方法得到包含键、值对的元组的列表来排序。由于字典本身是哈希的，所以是无序的。哈希表一般有很好的性能，因为用键查询相当快。序列类型用有序的数字键做索引将数据以数组的形式存储。一般索引值与所存储的数据毫无关系。还可以用另一种方式来存储数据:基于某种相关值，比如说一个字符串。我们在日常生活中一直这么做。把人们的电话号码按照他们的姓记录在电话簿上，按照时间在日历或约会薄上添加事件，等等。在这些例子中，你的键就是和数据项相关的值。哈希表是一种数据结构:它按照我们所要求的去工作。哈希表中存储的每一条数据，叫做一个值(value)，是根据与它相关的一个被称作为键(key)的数据项进行存储的。键和值合在一起被称为“键-值对”(key-value pairs)。哈希表的算法是获取键，对键执行一个叫做哈希函数的操作，并根据计算的结果，选择在数据结构的某个地址中来存储你的值。任何一个值存储的地址皆取决于它的键。正因为这种随意性，哈希表中的值是没有顺序的。你拥有的是一个无序的数据集。你所能获得的有序集合只能是字典中的键的集合或者值的集合。方法Keys()或values()返回一个列表，该列表是可排序的。你还可以用items()方法得到包含键、值对的元组的列表来排序。由于字典本身是哈希的，所以是无序的。哈希表一般有很好的性能，因为用键查询相当快。

hash表原理

哈希表（Hash table，也叫散列表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。
记录的存储位置=f(关键字)
这里的对应关系f称为散列函数，又称为哈希（Hash函数），采用散列技术将记录存储在一块连续的存储空间中，这块连续存储空间称为散列表或哈希表（Hash table）。
哈希表hashtable(key，value) 就是把Key通过一个固定的算法函数既所谓的哈希函数转换成一个整型数字，然后就将该数字对数组长度进行取余，取余结果就当作数组的下标，将value存储在以该数字为下标的数组空间里。（或者：把任意长度的输入（又叫做预映射， pre-image），通过散列算法，变换成固定长度的输出，该输出就是散列值。这种转换是一种压缩映射，也就是，散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，而不可能从散列值来唯一的确定输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。）
而当使用哈希表进行查询的时候，就是再次使用哈希函数将key转换为对应的数组下标，并定位到该空间获取value，如此一来，就可以充分利用到数组的定位性能进行数据定位。

什么是哈希表特点是什么

　　定义：哈希表，也叫散列表，是根据关键码值而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。

　　特点：

　　1、大大降低数据的存储和查找消耗的时间；

　　2、内存消耗较大；

　　3、使得编码更容易。

在哈希表、arraylist、数组、堆栈四个中哪个不是数据结构

其实这四个都是数据结构，哈希表是个使用散列算法的一种数据结构，arraylist其实就是顺序表，数组其实也是数据结构（书上有写的）。堆栈其实是两个数据结构，分别是堆和栈，栈是一种特殊的线性表，它是后进先出的。堆我不是很了解，如果要选的话，你选堆栈吧。

如何画出对应哈希表的数据结构

哈希表就是一种以 键-值(key-indexed) 存储数据的结构，我们只要输入待查找的值即key，即可查找到其对应的值。

哈希的思路很简单，如果所有的键都是整数，那么就可以使用一个简单的无序数组来实现：将键作为索引，值即为其对应的值，这样就可以快速访问任意键的值。这是对于简单的键的情况，我们将其扩展到可以处理更加复杂的类型的键。

使用哈希查找有两个步骤:

• 使用哈希函数将被查找的键转换为数组的索引。在理想的情况下，不同的键会被转换为不同的索引值，但是在有些情况下我们需要处理多个键被哈希到同一个索引值的情况。所以哈希查找的第二个步骤就是处理冲突

• 处理哈希碰撞冲突。有很多处理哈希碰撞冲突的方法，本文后面会介绍拉链法和线性探测法。

哈希表是一个在时间和空间上做出权衡的经典例子。如果没有内存限制，那么可以直接将键作为数组的索引。那么所有的查找时间复杂度为O(1)；如果没有时间限制，那么我们可以使用无序数组并进行顺序查找，这样只需要很少的内存。哈希表使用了适度的时间和空间来在这两个极端之间找到了平衡。只需要调整哈希函数算法即可在时间和空间上做出取舍。

数据结构问题：哈希表的存储结构是什么

哈希表的存储结构为散列函数。
散列技术是在记录的存储位置和它的关键字之间建立一个确定的对应关系f，使得每个关键字key对应一个存储位置f(key)。
这里把这种对应关系f称为散列函数，又称为哈希（Hash）函数。按这个思想，采用散列技术将记录存在在一块连续的存储空间中，这块连续存储空间称为散列表或哈希表。那么，关键字对应的记录存储位置称为散列地址。
散列技术最适合的求解问题是查找与给定值相等的记录。对于查找来说，简化了比较过程，效率会大大 提高。但是，散列技术部具备很多常规数据结构的能力，如比较同样的关键字，对应很多记录的情况，不适合用散列技术；散列表也不适合范围查找等等。
在理想的情况下，每一个关键字，通过散列函数计算出来的地址都是不一样的，可现实中，这只是一个理想。市场会碰到两个关键字key1 != key2，但是却有f(key1) = f(key2)，这种现象称为冲突。出现冲突将会造成查找错误，因此可以通过精心设计散列函数让冲突尽可能的少，但是不能完全避免。

哈希表—什么是哈希表

哈希表是一种数据结构～

哈希表可以存储各种类型的数据，当我们从哈希表中查找所需要的数据时，理想情况是不经过任何比较，一次存取便能得到所查记录， 那就必须在记录的存储位置和它的关键字之间建立一个确定的对应关系 f，使每个关键字和结构中一个唯一的存储位置相对应。 (关键字就是所要存储的数据，存储位置相当于数组的索引)

当然，可以把哈希表理解为一个数组，每个索引对应一个存储位置，哈希表的索引并不像普通数组的索引那样，从0到length-1，而是由关键字(数据本身)通过哈希函数得到

eg1. 将26个小写字母存储到数组  int a。

a对应a……以此类推。
那么，数组 int a 就是一个哈希表！

例1中，关键字(小写字母)是如何得到自己对应的索引(存储位置)的呢？

关键字的ASCII值减去a的ASCII值！
上面说过，关键字通过哈希函数得到索引，所以，f(ch)就是本例题的哈希函数。

这样，我们就在关键字和数字(存储位置)之间建立了一个确定的对应关系f。

关键字与数字是一一对应的，由于数组本身支持随机访问，所以，当查找关键字时，只需要O(1)的查找操作，也就是实现了不经过任何比较，一次便能得到所查记录。

哈希表中 哈希函数的设计 是相当重要的，这也是建哈希表过程中的关键问题之一。

假如，我们所要存储的数据其关键字是一个人的身份证号(18位数字)，这个时候我们该怎么计算关键字对应的索引呢？

比如一个人的身份证号是 411697199702076425，我们很难像例1那样直接让关键字与数字建立一一对应的关系，并且保证数字适合作为数组的索引。

在这种情况下，通过哈希函数计算出的索引，即使关键字不同，索引也会有可能相同。这就是 哈希冲突

当索引相同时，我们该怎么存储数据呢？如何解决哈希冲突，是我们建哈希表的另一个关键问题。

哈希表充分体现了空间换时间这种经典的算法思想。

关键字是大整数时，比如上面我们举的身份证号例子，411697199702076425

假如我们能开辟一个 999999999999999999 大的空间，这样就能直接把身份证号作为关键字存储到数组中，这样可以用O(1)时间完成各项操作

假如我们只有 1 的空间，我们需要把所有信息存储到这个空间中(也就是所有数据都会产生哈希冲突)，我们只能用O(n)时间完成各项操作

事实上，我们不可能开辟一个如此大的空间，也不可会开辟如此小的空间
无限空间时，时间为O(1)

1的空间时，时间为O(n)

而哈希表就是在二者之间产生一个平衡，即 空间和时间的平衡 。

1.哈希函数的设计

2.解决哈希冲突

3.哈希表实现时间和空间的平衡
后续会详细说明这三个关键问题～

理解哈希表

哈希表是种数据结构，它可以提供快速的插入操作和查找操作。

什么是Hash
Hash，一般翻译做“散列”，也有直接音译为“哈希”的，就是把任意长度的输入（又叫做预映射， pre-image），通过散列算法，变换成固定长度的输出，该输出就是散列值。这种转换是一种压缩映射，也就是，散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，而不可能从散列值来唯一的确定输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。

HASH主要用于信息安全领域中加密算法，它把一些不同长度的信息转化成杂乱的128位的编码,这些编码值叫做HASH值. 也可以说，hash就是找到一种数据内容和数据存放地址之间的映射关系。

数组的特点是：寻址容易，插入和删除困难；而链表的特点是：寻址困难，插入和删除容易。那么我们能不能综合两者的特性，做出一种寻址容易，插入删除也容易的数据结构？答案是肯定的，这就是我们要提起的哈希表，哈希表有多种不同的实现方法，我接下来解释的是最常用的一种方法——拉链法，我们可以理解为“链表的数组”，如图：

ctdwcdjxhxbsf01
左边很明显是个数组，数组的每个成员包括一个指针，指向一个链表的头，当然这个链表可能为空，也可能元素很多。我们根据元素的一些特征把元素分配到不同的链表中去，也是根据这些特征，找到正确的链表，再从链表中找出这个元素。

元素特征转变为数组下标的方法就是散列法。散列法当然不止一种，下面列出三种比较常用的：

1，除法散列法
最直观的一种，上图使用的就是这种散列法，公式：
index = value % 16
学过汇编的都知道，求模数其实是通过一个除法运算得到的，所以叫“除法散列法”。

2，平方散列法
求index是非常频繁的操作，而乘法的运算要比除法来得省时（对现在的CPU来说，估计我们感觉不出来），所以我们考虑把除法换成乘法和一个位移操作。公式：
index = (value * value) 》》 28 （右移，除以2^28。记法：左移变大，是乘。右移变小，是除。）
如果数值分配比较均匀的话这种方法能得到不错的结果，但我上面画的那个图的各个元素的值算出来的index都是0——非常失败。也许你还有个问题，value如果很大，value * value不会溢出吗？答案是会的，但我们这个乘法不关心溢出，因为我们根本不是为了获取相乘结果，而是为了获取index。

3，斐波那契（Fibonacci）散列法

平方散列法的缺点是显而易见的，所以我们能不能找出一个理想的乘数，而不是拿value本身当作乘数呢？答案是肯定的。

1，对于16位整数而言，这个乘数是40503
2，对于32位整数而言，这个乘数是2654435769
3，对于64位整数而言，这个乘数是11400714819323198485

这几个“理想乘数”是如何得出来的呢？这跟一个法则有关，叫黄金分割法则，而描述黄金分割法则的最经典表达式无疑就是著名的斐波那契数列，即如此形式的序列：0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144,233, 377, 610， 987, 1597, 2584, 4181, 6765, 10946，…。另外，斐波那契数列的值和太阳系八大行星的轨道半径的比例出奇吻合。

对我们常见的32位整数而言，公式：
index = (value * 2654435769) 》》 28

如果用这种斐波那契散列法的话，那上面的图就变成这样了：

ctdwcdjxhxbsf02
很明显，用斐波那契散列法调整之后要比原来的取摸散列法好很多。

适用范围
快速查找，删除的基本数据结构，通常需要总数据量可以放入内存。

基本原理及要点
hash函数选择，针对字符串，整数，排列，具体相应的hash方法。
碰撞处理，一种是open hashing，也称为拉链法；另一种就是closed hashing，也称开地址法，opened addressing。

扩展
d-left hashing中的d是多个的意思，我们先简化这个问题，看一看2-left hashing。2-left hashing指的是将一个哈希表分成长度相等的两半，分别叫做T1和T2，给T1和T2分别配备一个哈希函数，h1和h3。在存储一个新的key时，同 时用两个哈希函数进行计算，得出两个地址h1位置，哪一个 位置已经存储的（有碰撞的）key比较多，然后将新key存储在负载少的位置。如果两边一样多，比如两个位置都为空或者都存储了一个key，就把新key 存储在左边的T1子表中，2-left也由此而来。在查找一个key时，必须进行两次hash，同时查找两个位置。

问题实例（海量数据处理）
我们知道hash 表在海量数据处理中有着广泛的应用，下面，请看另一道百度面试题：
题目：海量日志数据，提取出某日访问百度次数最多的那个IP。
方案：IP的数目还是有限的，最多2^32个，所以可以考虑使用hash将ip直接存入内存，然后进行统计。

第三部分、最快的Hash表算法

接下来，咱们来具体分析一下一个最快的Hasb表算法。
我们由一个简单的问题逐步入手：有一个庞大的字符串数组，然后给你一个单独的字符串，让你从这个数组中查找是否有这个字符串并找到它，你会怎么做？有一个方法最简单，老老实实从头查到尾，一个一个比较，直到找到为止，我想只要学过程序设计的人都能把这样一个程序作出来，但要是有程序员把这样的程序交给用户，我只能用无语来评价，或许它真的能工作，但…也只能如此了。

最合适的算法自然是使用HashTable（哈希表），先介绍介绍其中的基本知识，所谓Hash，一般是一个整数，通过某种算法，可以把一个字符串”压缩” 成一个整数。当然，无论如何，一个32位整数是无法对应回一个字符串的，但在程序中，两个字符串计算出的Hash值相等的可能非常小

哈希表概念以及哈希冲突的处理

哈希表（散列表 Hash）是相对于线性表、树形结构的一种数据结构，它能在元素的存储位置和其关键字直接建立某种之间关系，那么在进行查找时，就无需做或者做很少次的比较，就能通过这个关系直接由关键字找到对对应的记录。这就是散列查找法（Hase Search）的思想，它通过对元素的关键字值进行某种运算，直接求出元素的地址。即使用关键字到地址的直接转换方法，而不需要反复比较。因此，散列查找法又叫杂凑法或者散列法。

选择一个好的散列函数可以在一定程度上减少冲突，但在实际应用中，很难完全避免发生冲突，所以选择一个有效的处理冲突的方法是散列表的另一个关键问题。
处理冲突的方法与散列表本身的组织形式有关。按组织形式的不同，通常分为两大类：开放地址法和链地址法。

开放地址法的基本思想是：把记录都存储在散列表数组中，当某一记录关键字key的初始散列地址H0=H(key)发生冲突时，以H0为基础，采取合适方法计算得到另一地址H1，如果H1仍然发生冲突，已H1位基础再求下一个地址H2，若H2仍然冲突，再求得H3，以此类推，直至Hk不发生冲突为止，则Hk为该记录在表中的散列地址。
根据计算方法，可以分为以下三种探测方法：

线性探测法会在出现在处理过程中发生冲突的发生第一个散列地址不同的记录争夺同一个后继散列地址的现象，称为二次聚集或者堆积。即在处理同义词的冲突过程中，又添加了非同义词的冲突。
它的优点是，只要散列表未满，就一定能找到一个不发生冲突的地址

而二次探测法和伪随机数探测法可以避免出现二次聚集现象，但是不保证一定能找到不发生冲突的地址。

链地址法的基本思想是：把具有相同散列地址的记录放在同一个单链表中，称为同义词链表。有m个散列地址就有m个单链表，同时用数组HT为头结点的单链表中。

数据结构-Hash

先看一下hash表的结构图：

哈希表（Hash table，也叫散列表），是根据键（Key）而直接访问在内存存储位置的数据结构。也就是说，它通过计算一个关于键值的函数，将所需查询的数据映射到表中一个位置来访问记录，这加快了查找速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表
白话一点的说就是通过把Key通过一个固定的算法函数（hash函数）转换成一个整型数字，然后就对该数字对数组的长度进行取余，取余结果就当作数组的下标，将value存储在以该数字为下标的数组空间里。

先了解一下下面几个常说的几个关键字是什么：
key ：我们输入待查找的值
value ：我们想要获取的内容
hash值 ：key通过hash函数算出的值（对数组长度取模，便可得到数组下标）
hash函数（散列函数） ：存在一种函数F，根据这个函数和查找关键字key，可以直接确定查找值所在位置，而不需要一个个遍历比较。这样就预先知道key在的位置，直接找到数据，提升效率。
即
地址index=F(key)
hash函数就是根据key计算出该存储地址的位置，hash表就是基于hash函数建立的一种查找表。

方法有很多种，比如直接定址法、数字分析法、平方取中法、折叠法、随机数法、除留余数法等，网上相关介绍有很多，这里就不重点说这个了

对不同的关键字可能得到同一散列地址， 即k1≠k2，而f(k1)=f(k2)，或f(k1) MOD 容量 =f(k2) MOD 容量 ，这种现象称为 碰撞 ，亦称 冲突 。
通过构造性能良好的hash函数，可以减少冲突，但一般不可能完全避免冲突，因此解决冲突是hash表的另一个关键问题。
创建和查找hash表都会遇到冲突，两种情况下解决冲突的方法应该一致。

这里要提到两个参数： 初始容量 ， 加载因子 ，这两个参数是影响hash表性能的重要参数。
容量 ： 表示hash表中数组的长度，初始容量是创建hash表时的容量。
加载因子 ： 是hash表在其容量自动增加之前可以达到多满的一种尺度（存储元素的个数），它衡量的是一个散列表的空间的使用程度。
loadFactor = 加载因子 / 容量
一般情况下，当loadFactor 《= 1时，hash表查找的期望复杂度为O(1).
对使用链表法的散列表来说， 负载因子越大，对空间的利用更充分，然后后果是查找效率的降低；如果负载因子太小，那么散列表的数据将过于稀疏，对空间造成严重浪费 。系统默认负载因子为0.75。

当hash表中元素越来越多的时候，碰撞的几率也就越来越高（因为数组的长度是固定的），所以为了提高查询的效率，就要对数组进行扩容。而在数组扩容之后，最消耗性能的点就出现了，原数组中的数据必须重新计算其在新数组中的位置，并放进去，这就是 扩容 。
什么时候进行扩容呢？当表中 元素个数超过了容量 * loadFactor 时，就会进行数组扩容。

Foundation框架下提供了很多高级数据结构，很多都是和Core Foundation下的相对应，例如NSSet就是和_CFSet相对应，NSDictionary就是和_CFDictionary相对应。 源码

这里说的hash并不是之前说的hash表，而是一个方法。为什么要有hash方法？
这个问题需要从hash表数据结构说起，首先看下如何在数组中查找某个成员

在数组未排序的情况下，查找的时间复杂度是O(n)（n为数组长度）。hash表的出现，提高了查找速度，当成员被加入到hash表中时，会计算出一个hash值，hash值对数组长度取模，会得到该成员在数组中的位置。
通过这个位置可以将查找的时间复杂度优化到O(1)，前提是在不发生冲突的情况下。
这里的hash值是通过hash方法计算出来的，且hash方法返回的hash值最好唯一
和数组相比，基于hash值索引的hash表查找某个成员的过程：

可以看出优势比较明显，最坏的情况和数组也相差无几。

重写person的hash方法和copyWithZone方法，方便查看hash方法是否被调用：

打印结果：

可以了解到： hash方法只在对象被添加到NSSet和设置为NSDictionary的key时被调用
NSSet添加新成员时，需要根据hash值来快速查找成员，以保证集合中是否已经存在该成员。
NSDictionary在查找key时，也是利用了key的hash值来提高查找的效率。
这里可以得到这个结论：
相等变量的hash结果总是相同的，不相等变量的hash结果有可能相同

根据数据结构可以发现set内部使用了指针数组来保存keys，可以从 源码 中了解到采用的是连续存储的方式存储。

NSSet添加key，key值会根据特定的hash函数算出hash值，然后存储数据的时候，会根据hash函数算出来的值，找到对应的下标，如果该下标下已有数据，开放定址法后移动插入，如果数组到达阈值，这个时候就会进行扩容，然后重新hash插入。查询速度就可以和连续性存储的数据一样接近O(1)了。

和上面的集合NSSet相比较，多了一个指针数组values。

通过比较集合NSSet和字典NSDictionary的 源码 可以知道两者实现的原理差不多，而字典则用了两个数组keys和values，说明这两个数据是被分开存储的。

通过源码可以看到，当有重复的key插入到字典NSDictionary时，会覆盖旧值，而集合NSSet则什么都不做，保证了里面的元素不会重复。
大家都知道，字典里的键值对key-value是一一对应的关系，从数据结构可以看出，key和value是分别存储在两个不同的数组里，这里面是如何对key、value进行绑定的呢？
首先 key利用hash函数算出hash值，然后对数组的长度取模，得到数组下标的位置，同样将这个地址对应到values数组的下标，就匹配到相应的value。 注意到上面的这句话，要保证一点， 就是keys和values这两个数组的长度要一致 。所以扩容的时候，需要对keys和values两个数组一起扩容。

对于字典NSDictionary设置的key和value，key值会根据特定的hash函数算出hash值，keys和values同样多，利用hash值对数组长度取模，得到其对应的下标index，如果下标已有数据，开放定址法后移插入，如果数组达到阈值，就扩容，然后重新hash插入。这样的机制就把一些不连续的key-value值插入到能建立起关系的hash表中。
查找的时候，key根据hash函数以及数组长度，得到下标，然后根据下标直接访问hash表的keys和values，这样查询速度就可以和连续线性存储的数据一样接近O(1)了。

参考文章： 笔记-数据结构之 Hash（OC的粗略实现）