Skip to content

Latest commit

 

History

History
18 lines (15 loc) · 1.3 KB

main.md

File metadata and controls

18 lines (15 loc) · 1.3 KB

LeetCode哈希表

定义

哈希表,也叫散列表,是可以通过关键字key访问映射表来得到value的地址,从而可以直接通过key获取其对应的value的值的数据结构,这个映射表也叫哈希函数,存放value的数组叫做哈希表。

给定表M,存在函数f(key),对任意给定的关键字值key,代入函数后若能得到包含该关键字的记录在表中的地址,则称表M为哈希(Hash)表,函数f(key)为哈希(Hash) 函数。

哈希冲突:不同的key通过哈希计算,得到了相同的地址,就会产生哈希冲突。

解决哈希冲突的方法:

  1. 链地址法:对Key通过哈希之后落在同一个地址上的值,做一个链表来进行存储同一个key对应的不同的值。
  2. 开放地址法:如果出现一个key2进行hash(key)后映射的位置与key1进行hash(key)后映射的位置一致(即发生了哈希冲突),那么从该位置往下寻找到第一个空位时将key2的数据放入。而从该位置往下寻找空闲位置的过程又称为探测。

题目