Collection之散列表(hash table)

链表和数组中元素是按一定次序进行排列的，散列表不在意元素的顺序，但是可以实现快速查找某个元素，散列表按照有利于其操作目的的原则组织数据。

散列表为每个对象计算一个整数，称为散列码（hash code），散列码是由对象的实例域产生的一个整数，具有不同数据域的对象将产生不同的散列码。

如果自己定义类，需要负责实现这个类的hashCode方法，自己实现的hashCode方法应该与equals方法兼容，即如果a.equals(b)为true，a必与b具有相同的散列码。散列码没有规律，如果x和y是两个不同的对象，那么x.hashCode()与y.hashCode基本上不会相同。String类使用下列算法计算散列码：

int hash = 0；
for(int i = 0; i<length();i++)
    hash = 31 * hash + charAt(i);

 由于hashCode方法定义在Object类中，因此每个对象都有一个默认的散列码，其值为对象的存储地址，看下面的例子：

String s = "Ok";
StringBuilder sb = new StringBuilder(s);
System.out.println(s.hashCode() + " " + sb.hashCode());
String t = new String("Ok");
StringBuilder tb = new StringBuilder(t);
System.out.println(t.hashCode() + " " + tb.hashCode());

 对应值为：

s      2556
sb    20526976
t       2556
tb     20527144

其中t和s具有相同的散列值，这是因为字符串的散列码是由内容导出的，而字符串sb和tb具有不同的散列码，是因为StringBuffer类中没有定义hashCode方法，它的散列码是由Object类的默认的hashCode方法导出的对象存储地址，所以不同。

如果重新定义equals方法，必须重新定义hashCode方法，以便用户可以将对象插入到散列表中。

hashCode方法应该返回一个整型数值，也可以是负数，并合理的组合实例域的散列码，以便能够让各个不同的对象产生的散列码更加均匀。

例如，下面Employee类的hashCode方法：

class Employee
{
    public int hashCode()
    {
    return 7 * name.hashCode()
    + 11 * new Double(salary).hashCode()
    + 13 * hireDay.hashCode();
    }
    . . .
}

 如果在数组类型的域，那么可以使用静态的Arrays.hashCode方法计算一个散列码，这个散列码由数组元素的散列码组成。

 

散列表可以用于实现几个重要的数据结构，其中最简单的是set类型，set是没有重复元素的元素集合，set的add方法首先在集中查找要添加的对象，如果不存在，就将这个对象添加进去。

Java集合类库提供了一个HashSet类，它实现了基于散列表的集，可以用add方法添加元素。contains方法已经被重新定义，用于在某个bucket中查找元素，不必查看集合中的所有的元素。

散列迭代器将依次访问所有的bucket，由于散列将元素分散在表的各个位置上，所以访问它们的顺序几乎是随机的，在不关心集合中元素的顺序时才应该使用HashSet。

下面的程序将从System.in读取单词，并添加到Set中，最后在打印部分单词及单词总数。可以使用一个普通文本文件示例进行运行测试，例如使用一个名称为 test.txt,里面包含几千个文本字符。

import java.util.*;
public class SetTest {

	/**
	 * 本程序通过使用HashSet散列集，计算文本文件中单词的个数并输出。
	 * @since 2010-09-03
	 * @author chensl
	 * @param args
	 */
	

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Set<String> words = new HashSet<String>();
		long totalTime = 0;
		
		Scanner in = new Scanner(System.in);
		while (in.hasNext())
		{
			String word = in.next();
			long callTime = System.currentTimeMillis();
			words.add(word);
			callTime = System.currentTimeMillis() - callTime;
			totalTime += callTime;
		}
		Iterator<String> iter = words.iterator();
		for (int i=1; i<=20; i++)
			System.out.println(iter.next());
		System.out.println("...");
		System.out.println(words.size()+" distinct words. " + totalTime + "milliseconds.");
	}
}

 

以上程序经过编译后，可以通过以下命令运行：

java SetTest < test.txt

 

输出结果类似于：

brave
attended
holding
begin.'
more.
REFUND
finished,'
lessons:
rumbling
lessons,
more,
'--it
cats.'
answered
'all
dropped,
'You
'Would
You're
THEIR
...
6014 distinct words. 16milliseconds.