作者:鐘文斌kebenJ | 来源:互联网 | 2023-05-19 18:06
今日,同事小胡同学提了一个关于HashCode的topic,特将一些简要的知识点记录下来散列表的基本思想就是将Entry(k,value)存放在table中,其位置由hash(k)决定
今日,同事小胡同学提了一个关于HashCode的topic,特将一些简要的知识点记录下来
散列表的基本思想就是将Entry(k,value)存放在table中, 其位置由 hash(k)决定.
由于hash(k)有可能冲突,下面介绍两种基本的解决hash冲突的方式
1. Chaining链接法
具有相同hash code的多个Entry,
插入时:将对应于同一个table位置 , 通过链表链接
查找时:将table中该位置的所有Entry取出(链表),一一比较
该方法被java 的Hashtable和 HashMap采用
2. Open Addressing开放寻址法
该方法将所有的元素都存放在table中。 这里没有链表。
插入或者查找时,将通过一次或者多次probing来决定元素在散列表中的位置
插入时:如果该位置已经保存了某个Entry,则probe下一个位置,探查方法函数设为 h(k, i) , i为第几次探查。多次探查的原因是探查后的位置可能也已经有Entry存在。
查找时:如果第i次探查的位置对应的Entry的key值与查找的key值相等,则结束。否则,probe下一个位置,直到为NIL.
三种常见的probing方法
2.1 linear probling
h(k, i) = ( h'(k) + i) mod m, i=0,1,..., m-1
h' 为普通的hash函数
m 为散列表长度
该方法将随着连续占用槽的增加,使得平均查找/插入时间增加
2.2 quadratic probing /kwɒˈdrætɪk/二次探查
h(k,i) = ( h'(k) + c1 * i + c2 * i*i ) mod m
c1, c2为辅助常数 != 0
该方法比线性探查好很多
2.3 双重散列
h(k, i) = ( h1(k) + i * h2(k) ) mod m
h1 , h2为辅助散列函数
初次探查位置为 h1(k), 后续的探查位置都在此基础上便宜量 h2(k)
这种方法被认为是相对比较理想的方式。
但是,同志们,java的hash map并没有使用此方法,而是Chaining法。
基本上可以认为,简单就是好的,大部分情况下我们的应用程序并不需要复杂的算法。
当然,有些情况下,这个地方可能程序performance tuning的一个点,但是请证明
1. 它确实极大影响的你的效率,同时没有别的更简单的tuning的地方
否则,不推荐改它!
思考,don't rush