19.3　散列表

前面介绍了链表和数组列表的知识，本节将介绍另一种数据结构：散列表。散列表跟链表和数组列表比起来，有什么不同？有什么优点和缺点呢？

在链表和数组列表中，要想查找某个特定的元素，就必须从头开始遍历。如果一个链表或者一个数组列表拥有的元素数量很大，那么就需要耗费大量的系统资源，去遍历整个数据结构。如何克服这个弊病？此时，就引进了另一个数据结构：散列表。

散列表通过“键-值对应”的形式存储元素。它是一个无序的数据结构，跟链表和数组列表不同，链表和数组列表都是有序的数据结构。

注意

有序数据结构的最大缺点就是无法控制元素出现的顺序，但同时正是因为它的无序，使得它可以快速查找特定的元素。

散列表通过一定的函数关系（散列函数）计算出对应的函数值，以这个值作为存储在散列表中的地址。从这个地址就可以直接获取这个元素，所以散列表对元素的查找非常高效。

当散列表中的元素存放的太满时，就必须再散列，将产生一个新的散列表。所有的元素放到新的散列表中，原先的散列表将被删除。在Java语言中，通过负载因子来决定何时对散列表进行散列，例如，如果负载因子是0.75，即散列表中已经有75%的位置被放满，那么将进行再散列。

负载因子越高（越接近1），内存使用率越高，元素的寻找时间越长。负载因子越低（越接近0），元素寻找的时间越短，内存浪费越多。散列表的默认负载因子是0.75。下一节将通过实例分析散列表的应用。