哈希表
什么是哈希表
哈希表（Hash table，也叫散列表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。
哈希表就是一种以 键-值(key-indexed) 存储数据的结构，我们只要输入待查找的值即key，即可查找到其对应的值。
- 键(key)：用于操作数据的标示，数组中的索引，或者字符串键等等。
- 槽(slot/bucket)：哈希表中用于保存数据的一个单元，也就是数据真正存放的容器。
- 哈希函数(hash function)：将key映射(map)到数据应该存放的slot所在位置的函数。
- 哈希冲突(hash collision)：哈希函数将两个不同的key映射到同一个索引的情况。
避免哈希冲突
拉链法
通过哈希函数，我们可以将键转换为数组的索引(0-M-1)，但是对于两个或者多个键具有相同索引值的情况，我们需要有一种方法来处理这种冲突。
一种比较直接的办法就是，将大小为M 的数组的每一个元素指向一个条链表，链表中的每一个节点都存储散列值为该索引的键值对，这就是拉链法。
线性探测法
开放寻址法中最简单的是线性探测法：当碰撞发生时即一个键的散列值被另外一个键占用时，直接检查散列表中的下一个位置即将索引值加1
阳光穿透心脏的1/2处
「爱情、让人受尽委屈。」
系统管理员
今天药忘吃喽~
傷城~
还没有评论，来说两句吧...