散列表

一、散列

1.散列技术是在记录的存储位置和它的关键字之间建立一个确定的对应关系f，使得每个关键字key 对应一个存储位置f (key)。查找时，根据这个确定的对应关系找到给定值key 的映射f (key) ，若查找集合中存在这个记录，则必定在f (key) 的位置上。这里我们把这种对应关系f 称为散列函数， 又称为哈希(Hash) 函数。按这个思想，采用散列技术将记录存储在一块连续的存储空间中，这块连续存储空间称为散列表或哈希表(Hash table)。 那么关键字对应的记录存储位置我们称为散列地址。

2.整个散列过程其实就是两步。

(1) 在存储时，通过散列函数计算记录的散列地址，并按此散列地址存储该记录。

(2) 当查找记录时，我们通过同样的散列函数计算记录的散列地址，按此散列地址访问该记录。由于存取用的是同一个散列函数， 因此结果当然也是相同的。

二、散列表也叫做哈希表，这种数据结构提供和键（key）和值（value）的映射关系。只要给出一个key，就可以高效查到它所匹配的value。

数组的查询效率高，数组可以通过下标，进行对元素的访问，散列表的本质也是一个数组。

三、通过某种方式，把key和数组下标进行转换，这种方式就叫哈希函数

例如java中HashMap：

index=HashCode（Key）%Array.length

key=001121时，

index=HashCode("001121")%Array.lenth=1420036703%8=7

四、写操作

通过哈希函数把key转换为数组下标X，如果数组下标X的对应位置没有元素，就把这个键值对填充进去，如果有元素，就使用下面的方法（解决哈希冲突）：

1.开放寻址法

当一个key通过哈希函数获得对应的数组下标记已被占用，就寻找下一个位置

例：下标为2，2有元素，就找3，3有元素就找4，4没元素，就存到4中

2.链表法（应用到java的HashMap中）

HashMap数组的每一个元素不仅是一个Entry（键值对）对象，还是一个链表的头节点。每一个Entry对象通过next指针指向它的下一个Entry节点。当新来的Entry映射到与之冲突的数组位置时，只需要插入到对应的链表中即可。

五、读操作

找数组下标下对应的元素，如key不对，找链表，顺着链表找

六、哈希表为何查询速度快？快在哪里？

1.数组存储数据：

现有一个数组，它里面每个单元存储的是数据的地址，假设它有100个单元，称它为P[100],现在我想把一百个数据（地址）放到里面，我们想把某个数据放到p的第几个单元完全是由是我们决定的，可以说想怎么放就怎么放，是一种乱放，既然是乱放，那么查找起来就比较耗时。

2.哈希表的存储数据：

哈希表同样也是个数组，同样需要存储100个数据，需要的就不是100个单元了，因为哈希表要把某个数据存放在某个单元不是随机的一个过程，而是算出来的，这个算法叫哈希函数。

比如要存储一个数据对：

张三 1882356

李四  23456789

王五  58856456

张三经过哈希函数算出来的值是138，那么哈希表最少需要138个单元，因为张三对应的数据1882356要存储在指针数组的p[138]的位置上。

李四经过哈希函数算出来的值是500，那么2356789这个数据就要存放在p[500]这个位置上。

所以说，"数据的地址放在数组的哪个单元格是算出来的，是有迹可寻的，并不是想放在哪里就放在哪里"。

那查找的时候就好查找了，你要查找张三对应的数据，直接把张三用哈希函数算一下，得到138，张三的数据就在p[138]这个位置上，所以一下就找到了

小结：

1.什么是数组？

数组是由有限个相同类型的变量所组成的有序集合，它的物理存储方式是顺序存储、访问方式是随机访问。利用下标查找数组元素的时间复杂度是O(1)，中间插入、删除数组元素的时间复杂度是O(n)。

2.什么是链表？

链表是一种链式数据结构，由若干节点组成，每个节点包含指向下一节点的指针。链表的物理存储方式是随机存储，访问方式是顺序访问。查找链表节点的时间复杂度是O(n)，中间插入、删除节点的时间复杂度是O(1)。

3.什么是栈？

栈是一种线性逻辑结构，可以用数组实现，也可以用链表实现。栈包含入栈和出栈操作，遵循先入后出的原则。

4.什么是队列？

队列也是一种线性逻辑结构，可以用数组实现，也可以用链表实现。队列包含入队和出队操作，遵循先入先出的原则。

5.什么是散列表？

散列表也叫哈希表，是存储Key-Value映射的集合。对于某一个Key，散列表可以在接近O(1)的时间内进行读写操作。散列表通过哈希函数实现Key和数组下标的转换，通过开放寻址法和链表法来解决哈希冲突。