字典实现的原理
2019-01-29 本文已影响51人
微笑_d797
字典是根据hash表来映射key与value之间的存储的
取值是无须遍历数组而是将key代入到函数中得到其中的value
例如 一种简单的算法
哈希函数 f(key) = (Ord(key的第一个字母) - 97)/2
赵钱孙李 对应的key为
| zhao | qian | sun | li |
|---|---|---|---|
| 26 | 17 | 19 | 12 |
在整个数组长度中他们所处的位置为
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| - | - | - | - | - | - | li | - | qian | sun | - | - | - | zhao |
那么当取值时只需要知道key 例如“zhao” 那么 f(zhao) = Ord(zhao)/2 = 13 的到13 无须进行遍历那么时间复杂度即为1 倘若多出一个相同key的值来那么需要给他一个增量例如多处一个key 为zhang f(key) = (Ord(zhang) - 97)/2 = 13 那么就需要+1 即在他的14的位置上。
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| - | - | - | - | - | - | li | - | qian | sun | - | - | - | zhao | zhang |
上面只是一种简单的算法例如还有 MD5，SHA1，SHA256 等算法都是哈希算法
哈希函数的缺点
1.如果哈希表中本来箱子就比较多，扩容时需要重新哈希并移动数据，性能影响较大。
2.如果哈希函数设计不合理，哈希表在极端情况下会变成线性表，性能极低。
