算法4B-----散列

散而列之

建立快速查询的索引

BC[j,‘x’]，j相当于身份证号，

call-by-value

需要查电话簿才能拨打电话

建立一个表格，直接输索引，就可以打出响应的值

java:hashMap+hashTable

可以把key-value存储到容器中通过key直接获取value

perl:%hash type

python:dictionary class

ruby:hash table

hashing:table+function

昨天的例子

BC表，字符集中有多少个字符就有多少项中间的每一项都记了一个shift[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-rjpaqaHj-1601905457488)(C:\Users\liusiping\AppData\Roaming\Typora\typora-user-images\image-20201005195132162.png)]但是unicode这么大集合的字符串就不可能一下子开这么大的数组

清华大学的电话簿

新建一个数组00000000~99999999首先开不了这么大的数组，其次利用率太低好处查询O（1），坏处没有这么大的空间

解决思路

建一个虚拟的表，假想开那么大的空间

分成两步

1.经过一次函数计算才映射到散列表上

2.从散列表上再去快速查询，这个散列表是10的(4~5)次方级别<<10^8，几万的数量

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-lZL7ofwo-1601905457497)(C:\Users\liusiping\AppData\Roaming\Typora\typora-user-images\image-20201005195829518.png)]

取一个素数90001，数组容量是90000，通过取模运算