描述:将M-bit的数据映射到N-bit(N小于M),这个映射的过程和方法就是hash。
作用:用来查表,节省memory空间,提高查表的性能(硬件上)
问题:
1. M到N的映射两个数据空间不一样,必然带来在映射后空间的冲突。
2.需要对使用hash查表的数据(M)进行测试,保证实际使用到的数据不会导致在映射后的冲突,或者冲突的概率比较小。
3.冲突发生后,需要找到一种合理方法,解决冲突,通常使用链表。链表的级数多少,与冲突的实际情况有关,也要考虑硬件链表的查表代价(访问代价和memory的容量消耗)。