chap 1-7 数论算法-全域哈希

1. 哈希表

数论算法在哈希函数的设计方面也有应用。假设在编写网络服务应用时，我们需要维护一个动态变化的客户的IPv4地址的list，如何快速地查询某个IP呢？一个最快的方法是建立大小为$2^{32}$的array，以IP作为index。虽然很快，但是会非常浪费内存，大多数内存可能都是空的。还有一个方法是使用链表，但是查询速度很慢，与客户个数成正比。使用哈希的方法能使占用内存的大小与客户数量成正比，同时获得较快的查询速度。