HashMap与HashTable

                                               HashMap与HashTable

 1、Hashtable与HashMap的相同之处 （http://wenku.baidu.com/view/921383d176eeaeaad1f330f5.html）

    Java包含两个类，java.util.Hashtable 和java.util.HashMap，它们提供了一个多种用途的hashtable机制。Hashtable和HashMap对象可以让你把一个key和一个value结合起来，并用put() 方法把这对key/value输入到表中。然后你可以通过调用get()方法，把key作为参数来得到这个value（值）。只要满足两个基本的要求，key和value可以是任何对象。注意，因为key和value必须是对象，所以原始类型（primitive types）必须通过运用诸如Integer(int)的方法转换成对象。下面是一段简单的示例代码：

1. 先创建一个hashtable，保存了1, 2, 3三个对象。

 

 

Hashtable numbers = new Hashtable();

numbers.put("one", new Integer(1));

numbers.put("two", new Integer(2));

numbers.put("three", new Integer(3));

 

 

 

2. 查找

 

Integer n = (Integer)numbers.get("two");

if (n != null) {

System.out.println("two = " + n);

}

 

 

        为了将一个特定类的对象用做一个key，这个类必须提供两个方法，equals() 和 hashCode()。这两个方法在java.lang.Object中，所以所有的类都可以继承这两个方法；但是，这两个方法在Object类中的实现一般没什么用，所以你通常需要自己重载这两个方法。

Equals()方法把它的对象同另一个对象进行比较，如果这两个对象代表相同的信息，则返回true。该方法也查看并确保这两个对象属于相同的类。如果两个参照对象是完全一样的对象，Object.equals()返回true，这就说明了为什么这个方法通常不是很适合的原因。在大多数情况下，你需要一个方法来一个字段一个字段地进行比较，所以我们认为代表相同数据的不同对象是相等的。

hashCode()方法通过运用对象的内容执行一个哈希函数来生成一个int值。Hashtable和HashMap用这个值来算出一对key/value位于哪个bucket（哈希元）（或列表）中。

如果你想创建一个hashtable，这个hashtable运用你自己定义的一个类的对象作为key，那么你应该确信这个类的equals()和hashCode()方法提供有用的值。首先查看你扩展的类，确定它的实现是否满足你的需求。如果没有，你应该重载方法。

任何equals()方法的基本设计约束是，如果传递给它的对象属于同一个类，而且它的数据字段设定为表示同样数据的值，那么它就应该返回true。你也应该确信，如果传递一个空的参数给该方法，那么你的代码返回false：public boolean equals(Object o)

 

	{		
		if ( (o == null) || !(o instanceof myClass)){
			 return false;
		}
	} 

 

 

        另外，在设计一个hashCode()方法时，应该记住一些规则。首先，该方法必须为一个特定的对象返回相同的值，而不管这个方法被调用了多少次（当然， 只要对象的内容在调用之间没有改变，在将一个对象用做一个hashtable的key时，应该避免这一点）。第二，如果由你的equals()方法定义的 两个对象是相等的，那么它们也必须生成相同的哈希码。第三，这更像是一个方针，而不是一个原则，你应该设法设计方法，使它为不同的对象内容生成不同的结 果。如果偶尔不同的对象正好生成了相同的哈希码，这也不要紧。但是，如果该方法只能返回范围在1到10的值，那么只能用10个列表，而不管在 hashtable中有多少个列表。

String类已经按照要求实现了hashCode()，因为在设计自己的关键字类时，可以调用String.hash()，但是StringBuffer()不能用作关键字类，其并没按要求实现hashCode().

2 、Hashtable和HashMap不同之处：

       Hashtable和HashMap类有三个重要的不同之处。第一个不同主要是历史原因。Hashtable是基于陈旧的Dictionary类的，HashMap是Java 1.2引进的Map接口的一个实现。

       也许最重要的不同是Hashtable的方法是同步的，而HashMap的方法不是。这就意味着，虽然你可以不用采取任何特殊的行为就可以在一个多线程的应用程序中用一个Hashtable，但你必须同样地为一个HashMap提供外同步。一个方便的方法就是利用Collections类的静态的synchronizedMap()方法，它创建一个线程安全的Map对象，并把它作为一个封装的对象来返回。这个对象的方法可以让你同步访问潜在的HashMap。

        第三点不同是，只有HashMap可以让你将空值作为一个表的条目的key或value。HashMap中只有一条记录可以是一个空的key，但任意数量的条目可以是空的value。这就是说，如果在表中没有发现搜索键，或者如果发现了搜索键，但它是一个空的值，那么get()将返回null。如果有必要，用containKey()方法来区别这两种情况。

        一些资料建议，当需要同步时，用Hashtable，反之用HashMap。但是，因为在需要时，HashMap可以被同步，HashMap的功能比 Hashtable的功能更多，而且它不是基于一个陈旧的类的，所以有人认为，在各种情况下，HashMap都优先于Hashtable。

3.Hashtable性能

       影响hashtable功效的主要因素就是表中列表的平均长度，因为平均搜索时间与这个平均长度直接相关。很显然，要减小列表平均长度，你必须增加hashtable中列表(Hash值的个数)的数量；如果列表数量非常大，以至于大多数列表或所有列表只包含一条记录，你就会获得最佳的搜索效率。 然而，这样做可能太过分了。如果你的hashtable的列表数远远多于数据条目，那你就没有必要做这样的内存花费了，而在一些情况下，人们也不可能接受 这样的做法。

       在我们前面的例子中，我们预先知道我们有多少条记录1,000。知道这点后，我们就可以决定我们的hashtable应该包含多少个列表，以便达成搜索速 度和内存使用效率之间最好的折中方式。然而，在许多情况下，你预先不知道你要处理多少条记录；数据被读取的文件可能会不断扩大，或者记录的数量可能一天一 天地发生很大的变化。

        随着条目的增加，Hashtable和HashMap类通过动态地扩展表来处理这个问题。这两个类都有接受表中列表最初数量的构造器，和一个作为参数的负载系数（load factor）：

        public Hashtable(int initialCapacity,float loadFactor)

        public HashMap(int initialCapacity,float loadFactor)

       将这两个数相乘计算出一个临界值。每次给哈希表添加一个新的条目时，计数就被更新，当计数超过临界值时，表被重新设置（rehash)。（列表数量增加到 以前数量的两倍加1，所有的条目转移到正确的列表中。）缺省的构造器设定最初的容量为11，负载系数是0.75，所以临界值是8。当第九条记录被添加到表 中时，就重新调整哈希表，使其有23个列表，新的临界值将是17（23*0.75的整数部分）。你可以看到，负载系数是哈希表中平均列表数量的上限，这就 意味着，在缺省情况下，哈希表包含不只一条记录的列表会很少。比较我们最初的例子，在那个例子中，我们有1,000条记录，分布在10个列表中。如 果我们用这种方法，这个表将会扩展到含有1,500多个列表。但你可以控制这点。如果用负载系数相乘的列表数量大于你处理的条目数，那么表永远不会重制，所 以我们可以仿效下面的例子：// Table will not rehash until it

// has 1,100 entries (10*110):

Hashtable myHashTable = new Hashtable(10, 110.0F);

       这种方法（使用大的负载系数）可能很有用，因为重新设置很占用计算时间，而这种方法可以保证永远不会发生重新设置这种情况。而使用缺省的方法会浪费内存和增加额外的搜索时间。

注意，虽然调用put()可以使表增大（列表数量增加），调用remove()不会有相反的结果。所以，如果你有一个大的表，而且从中删除了大部分条目，结果你会有一个大的但是大部分是空的表。

4.关于Properties

          有时侯，你可能想用一个hashtable来映射key的字符串到value的字符串。DOS、Windows和Unix中的环境字符串就有一些例子，如 key的字符串PATH被映射到value的字符串C:WINDOWS;C:WINDOWSSYSTEM。Hashtables是表示这些的一个简单的方 法，但Java提供了另外一种方法。Java.util.Properties类是Hashtable的一个子类，设计用于String keys和values。Properties对象的用法同Hashtable的用法相象，但是类增加了两个节省时间的方法，Store()方法把一个Properties对象的内容以一种可读的形式保存到一个文件中。Load()方法正好相反，用来读取文件，并设定Properties对象来包含keys和values。

         注意：因为Properties扩展了Hashtable，你用父类的put()方法添加不是String对象的keys和values，但这是不安全的，因为如果你将store()用于一个不包含String对象的Properties对象，store()将失败。作为put()和get()的替代，你应该用setProperty()和getProperty()，它们只用String参数。

5.关于Hash冲突

Hash基本知识：

(1)哈希表(散列表，杂凑表)

根据设定的哈希函数和处理冲突的方法，将一组关键字(key)映像到一个有限的连续的地址集上，并以关键字在地址集中的象作为记录在表中的存储位置，这种表称为哈希表，又叫散列表，杂凑表。

(2)哈希函数

常用除留余数法。H(key) = key MOD p。

(3)冲突

什么是冲突？把一个对象的关键字(key)Hash后发现这个Hash值，发现该值在散列表中已经有其他记录对应了，这时就发生了冲突

H(key₁)=H(key₂)，且key₁≠key₂，称冲突。

处理冲突的方法：当H(key)处已有记录，出现冲突，如何处理？

 

Hash冲突：Hash冲突解决办法：（http://hi.baidu.com/zkheartboy/blog/item/b181470f301b79296159f3d0.html）       

1、开放定址法(发现该位置被占了就向后找，直到找到一个空位，或找到自己的key(已存在))
    　用开放定址法解决冲突的做法是：当冲突发生时，使用某种探查(亦称探测)技术在散列表中形成一个探查测序列。沿此序列逐个单元地查找，直到找到给定 的关键字，或者碰到一个开放的地址(即该地址单元为空)为止（若要插入，在探查到开放的地址，则可将待插入的新结点存人该地址单元）。查找时探查到开放的 地址则表明表中无待查的关键字，即查找失败。
注意：
①用开放定址法建立散列表时，建表前须将表中所有单元(更严格地说，是指单元中存储的关键字)置空。
②空单元的表示与具体的应用相关。
    　按照形成探查序列的方法不同，可将开放定址法区分为线性探查法、线性补偿探测法、随机探测等。
（1）线性探查法(Linear Probing)
该方法的基本思想是：
    将散列表T[0..m-1]看成是一个循环向量，若初始探查的地址为d(即h(key)=d)，则最长的探查序列为：
        d，d+l，d+2，…，m-1，0，1，…，d-1
    　即:探查时从地址d开始，首先探查T[d]，然后依次探查T[d+1]，…，直到T[m-1]，此后又循环到T[0]，T[1]，…，直到探查到T[d-1]为止。
探查过程终止于三种情况：
    　(1)若当前探查的单元为空，则表示查找失败（若是插入则将key写入其中）；
       (2)若当前探查的单元中含有key，则查找成功，但对于插入意味着失败；
    　(3)若探查到T[d-1]时仍未发现空单元也未找到key，则无论是查找还是插入均意味着失败(此时表满)。
利用开放地址法的一般形式，线性探查法的探查序列为：
        h_i=(h(key)+i)％m 0≤i≤m-1 //即d_i=i
用线性探测法处理冲突，思路清晰，算法简单，但存在下列缺点：
① 处理溢出需另编程序。一般可另外设立一个溢出表，专门用来存放上述哈希表中放不下的记录。此溢出表最简单的结构是顺序表，查找方法可用顺序查找。
② 按上述算法建立起来的哈希表，删除工作非常困难。假如要从哈希表 HT 中删除一个记录，按理应将这个记录所在位置置为空，但我们不能这样做，而只能标上已被删除的标记，否则，将会影响以后的查找。
③ 线性探测法很容易产生堆聚现象。所谓堆聚现象，就是存入哈希表的记录在表中连成一片。按照线性探测法处理冲突，如果生成哈希地址的连续序列愈长 ( 即不同关键字值的哈希地址相邻在一起愈长 ) ，则当新的记录加入该表时，与这个序列发生冲突的可能性愈大。因此，哈希地址的较长连续序列比较短连续序列生长得快，这就意味着，一旦出现堆聚 ( 伴随着冲突 ) ，就将引起进一步的堆聚。
（2）线性补偿探测法
线性补偿探测法的基本思想是：
将线性探测的步长从 1 改为 Q ，即将上述算法中的 j ＝ (j ＋ 1) % m 改为： j ＝ (j ＋ Q) % m ，而且要求 Q 与 m 是互质的，以便能探测到哈希表中的所有单元。
【例】 PDP-11 小型计算机中的汇编程序所用的符合表，就采用此方法来解决冲突，所用表长 m ＝ 1321 ，选用 Q ＝ 25 。

（3）随机探测
随机探测的基本思想是：
将线性探测的步长从常数改为随机数，即令： j ＝ (j ＋ RN) % m ，其中 RN 是一个随机数。在实际程序中应预先用随机数发生器产生一个随机序列，将此序列作为依次探测的步长。这样就能使不同的关键字具有不同的探测次序，从而可以避 免或减少堆聚。基于与线性探测法相同的理由，在线性补偿探测法和随机探测法中，删除一个记录后也要打上删除标记。

2、拉链法
（1）拉链法解决冲突的方法
    　拉链法解决冲突的做法是：将所有关键字为同义词的结点链接在同一个单链表中。若选定的散列表长度为m，则可将散列表定义为一个由m个头指针组成的指针数 组T[0..m-1]。凡是散列地址为i的结点，均插入到以T[i]为头指针的单链表中。T中各分量的初值均应为空指针。在拉链法中，装填因子α可以大于 1，但一般均取α≤1。
【例】设有 m ＝ 5 ， H(K) ＝ K mod 5 ，关键字值序例 5 ， 21 ， 17 ， 9 ， 15 ， 36 ， 41 ， 24 ，按外链地址法所建立的哈希表如下图所示：

          
（2）拉链法的优点
与开放定址法相比，拉链法有如下几个优点：
①拉链法处理冲突简单，且无堆积现象，即非同义词决不会发生冲突，因此平均查找长度较短；
②由于拉链法中各链表上的结点空间是动态申请的，故它更适合于造表前无法确定表长的情况；
③开放定址法为减少冲突，要求装填因子α（记录数/hash表大小）较小，故当结点规模较大时会浪费很多空间。而拉链法中可取α≥1，且结点较大时，拉链法中增加的指针域可忽略不计，因此节省空间；
④在用拉链法构造的散列表中，删除结点的操作易于实现。只要简单地删去链表上相应的结点即可。而对开放地址法构造的散列表，删除结点不能简单地将被删结 点的空间置为空，否则将截断在它之后填人散列表的同义词结点的查找路径。这是因为各种开放地址法中，空地址单元(即开放地址)都是查找失败的条件。因此在 用开放地址法处理冲突的散列表上执行删除操作，只能在被删结点上做删除标记，而不能真正删除结点。

（3）拉链法的缺点
    　拉链法的缺点是：指针需要额外的空间，故当结点规模较小时，开放定址法较为节省空间，而若将节省的指针空间用来扩大散列表的规模，可使装填因子变小，这又减少了开放定址法中的冲突，从而提高平均查找速度。

 

 

3、再Hash法

 这种方法是同时构造多个不同的哈希函数：

    H_i=RH₁（key）  i=1，2，…，k

 

当哈希地址H_i=RH₁（key）发生冲突时，再计算H_i=RH₂（key）……，直到冲突不再产生。这种方法不易产生聚集，但增加了计算时间。

 

4、建立公共溢出区

这种方法的基本思想是：将哈希表分为基本表和溢出表两部分，凡是和基本表发生冲突的元素，一律填入溢出表

CourrentHashMap：（http://www.iteye.com/topic/1103980）

         看了ConcurrentHashMap的实现, 使用的是拉链法.

        虽然我们不希望发生冲突，但实际上发生冲突的可能性仍是存在的。当关键字值域远大于哈希表的长度，而且事先并不知道关键字的具体取值时。冲突就难免 会发 生。另外，当关键字的实际取值大于哈希表的长度时，而且表中已装满了记录，如果插入一个新记录，不仅发生冲突，而且还会发生溢出。因此，处理冲突和溢出是 哈希技术中的两个重要问题。