//puttable[h%table.length]=value;//gete=table[h%table.length];直接取模是我们最容易想到的获取下标的方法,但是最高效的方法吗?我们知道计算机中的四则运算最终都会转换成二进制的位运算我们可以发现,只有数是1时,运算的结果与被数一致
11=1;01=0;10=0;00=0;这同样适用于多位操作数
=;==10;=;==11;00=;==0;00=;==0;我们是不是又有所发现:与得到的结果一样,也就是冲突(碰撞)了,那么10和11对应的value会在同一个链表中,而table的有些位置则永远不会有元素,这就导致table的空间未得到充分利用,同时还降低了put和get的效率(对比数组和链表);由于是2个数进行运算,所以结果由这两个数决定,如果我们把这两个数都做下限制,那得到的结果是不是可控制在我们想要的范围内了?我们需要利用好运算的特点,当右边的数的低位二进制是连续的1,且左边是一个均匀的数(需要hash方法实现,尽量保证key的h唯一),那么得到的结果就比较完美了。低位二进制连续的1,我们很容易想到2^n-1;而关于左边均匀的数,则通过hash方法来实现,这里不做细究了。更多面试题,欢迎