1. 从线性表说起
我们知道，线性表是最简单的数据结构，主要分为两类：顺序表和链表。其中，顺序表的突出优点是索引查找十分高效，然而一般不支持动态扩展，常用简单的数组实现；而链表的突出优点是支持动态扩展，即增删处理十分方便，然而查找的代价相对较高，每次需要从头开始一个个的查找，另外，链表实现时需要存储额外的引用，空间代价相对较高。
那能不能有一种数据结构能结合顺序表和链表的优点呢？哈希表，又称散列表，就有这样的特点。实现机理上，它可以看做顺序表和链表的结合体；功能上，又能很好的支持"增删查改"基本操作。
2. 散列
散列，有映射之意，映射又可以看作函数的泛化，从命名可以猜测出，哈希表与函数或许有着千丝万缕的联系，事实正是如此。一方面，哈希表的基本功能与其他数据结构比如集合类似，都是来存储对象的，只是哈希表在存储每一个对象时需要同时存储对象的Key值，对象的Key值可以看做对象的身份标识，就好比每一个人有一个身份证一样，这样不管人在哪里，有了身份证号码就能很快的查找出这个人的基本信息。Key值的作用与此类似，有了Key值，就可以按照一定的规则生成相应的哈希码，根据哈希码就能很快的查找出相应的对象。另一方面，Key和Value之间的对应关系，正是一种映射关系的体现，对于有限范围内随机出现的Key值，我们希望通过设计的映射规则，得到的Value值的分布也尽可能的随机分布，即随机均匀的定义域（Key的值空间）变换到随机均匀的值域（Value的值空间）。
考虑到性能的问题，实际设计的哈希表一般不是装满的，有容量和装满程度的限制，二者同时来控制表的动态扩展。在哈希表中，装载因子（Load Factor）用来表示哈希表的装满程度，容量（Capacity）来给出哈希表的初始规模。
3. 哈希码
哈希码（HashCode），即哈希编码，是一种映射规则，在Java中，若要将对象存储到 Hashtable 上，就需要将其关键字 key 映射到一个整型数据，成为 key 的哈希码。如何让计算机辨别出同一个类的两个对象的不同呢？也就是说为了让对象具有比较好的可分辨性（equals()方法），可以通过自定义哈希码生成算法（重写hashCode()方法）来实现。
下一个基本问题：hashCode()方法的设计。
原文：http://www.cnblogs.com/babecafe/p/5267594.html