散列hash及冲突解决

数组:寻址容易,插入和删除困难
链表:寻址困难,插入和删除容易

散列方式

  • 除法散列法
    index = value % 16

  • 平方散列法
    index = (value*value) >> 28

  • 斐波拉契散列法
    (1)对于16位整数而言,这个乘数是40503
    (2)对于32位整数而言,这个乘数是2654435769
    (3)对于64位整数而言,这个乘数是11400714819323198485
    index = (value*2654435769)>>28

hash冲突解决

拉链法

此处输入图片的描述