Hashing

目的

为了得到更快的添加数据和判断该数据结构是否包含某数据的速度(即add&contain的速度).

尝试

(一)

我们可以设想一个boolean数组,我们每添加一个非负整数,就把它当成数组的索引,然后把对应位置的数据改为true.这样我们就得到了一个add&contain都为O(1)的数据结构. 那如果我们要处理字符串呢?比如”cat” “dog”,一个自然的想法是我们可以把首字母转换为数字来当作索引,比如c对应3,d对应4.我们就又可以得到一个add&contain字符串都为O(1)的数据结构.但这个结构存在非常明显的问题: ”?” 之类的符号怎么存储? 并且”cat” “come” “candy”都是c开头的,于是就发生了”碰撞”.

(二)

继续想办法解决,我们知道存在ASCII表,于是我们就能把所有的数字,字母,符号都转化为数字,为了避免碰撞,我们还可以对数据进行固定的处理,比如base27,即个位 * 27^0, 十位 * 27^1,以此类推可以得到一个重复率较低的数字. 比如”cat”得到9999就把索引为9999的数据改为true,“12!sda”得到88888就把对应的数据改为true. 那汉字呢?好办,换个字符集不就可以了,比如unicode. 但在又存在一个问题,为了存储索引为9999的数据,我们不得不创建一个大小为9998的数组,而这个数组中存在大量的空缺,这就导致的非常多的内存浪费. 并且由于我们得到的索引数太大了,甚至会频繁导致溢出. 有没有办法让我们在大小为10的数组里也能根据索引存储这些数据呢?

(三)

用 ”%” ! 我们把直接得到的哈希值进行模运算,数组size为10就 %10,size多少就%上多少.这样就能正常的存储在size比较小的数组中了. 正常存储后碰撞的问题又进入到我们的视野,99,899,8889都会得到9这个索引,那怎么办?,如何存储这些碰撞的数据? 设计一个优秀的哈希函数就非常重要了,既需要保证相同的数据一定能得到相同的哈希值,又需要尽量降低不同数据得到相同哈希值的概率,不过不用担心,有人帮我们设计好了.java内置有一个.hashcode()函数,我们可以直接通过这个得到哈希值.

(四)

这时来看我们最初的布尔数组就有些过时了,大伙都在进化怎么就你拉跨呢? 那我们就干脆用数组存储LinkedList,得到相同索引的数据全放在这个链表中,但与此同时我们的contain函数也退化了,因为我们不仅要通过数据来得到哈希值对应的索引,我们还需要遍历对应数组里的元素来查找到底有没有这个数据.即为O(Q),Q就是最长链表的长度. 为了改善这个问题,我们需要尽量降低Q的大小,所以就用到了数组的扩容,毕竟数组扩大了,数据也就更分散了,链表的长度也会随之降低.那究竟什么时候扩容呢? 这时我们要用到一个叫做负载因子的东西来判断数组扩容的时机. 当目前的负载因子大小达到我们规定的大小时就会进行数组扩容,java的默认值为0.75. 也就是说,如果我们的元素分布的足够均匀,比如,每个链表只有一个元素,我们依然可以得到O(1)