Hashtable 源码阅读

今天复习一下 Hashtable 的基本原理。看了下源码，找了点资料。

下面这个文章，写得相当完整了。
http://tonylian.iteye.com/blog/384080
以下简称引文。

这篇文章是以 .net 为例的。

java 的有一点区别。

一、初始容量 和加载因子
Hashtable 的实例有两个参数影响其性能：初始容量和加载因子。容量 是哈希表中桶 的数量，初始容量 就是哈希表创建时的容量。注意，哈希表的状态为 open：在发生“哈希冲突”的情况下，单个桶会存储多个条目，这些条目必须按顺序搜索。加载因子 是对哈希表在其容量自动增加之前可以达到多满的一个尺度。初始容量和加载因子这两个参数只是对该实现的提示。关于何时以及是否调用 rehash 方法的具体细节则依赖于该实现。

通常，默认加载因子(.75)在时间和空间成本上寻求一种折衷。加载因子过高虽然减少了空间开销，但同时也增加了查找某个条目的时间（在大多数 Hashtable 操作中，包括 get 和 put 操作，都反映了这一点）。

默认初始化，初始容量为 11，加载因子为 0.75。

	public Hashtable() {
		this(11, 0.75f);
	}

引文中有如下描述：
数组容量 Array.Length 期望是一个 "比较大的质数", 这样 f(K) = HashOf(K) % Array.Length 取模运算之后得出的数冲突机会较小. 想象一个极端例子, 假设 Array.Length = 2, 则只要 HashOf(K) 是偶数, f(k) 都为 0. 所以说哈希表的实际容量一般都是有规律的, 和数组不一样, 不能任意设置.

二、hashtable 的存取

引文中描述到：
Hashtable 中的实际数据都存储在一个内部 Array 中 (当然和普通数组一样, 有固定容量, 上下标, 以数字索引存取), 当用户希望取得 Hashtable[K] 值的时候, Hashtable 进行如下处理:

[1] 为了保证 f(K) 的取值范围在  0 <= f(K) < Array.Length, 函数 f 的关键步骤是取模运算, 算得实际数据存储位置为 f(K) = HashOf(K) % Array.Length, 至于这个 HashOf(K) 怎么算出来的, 简单举例来说她可以取关键字的 ASCII 码根据一定规则运算得到.

[2] 如果发生多个 K 值的哈希值重复, 即 f(K1) = f(K2), 而 f(K1) 位置已经有数据占用了, Hashtable 采用的是 "开放定址法" 处理冲突, 具体行为是把 HashOf(K2) % Array.Length 改为 (HashOf(K2) + d(K2)) % Array.Length , 得出另外一个位置来存储关键字 K2 所对应的数据, d 是一个增量函数. 如果仍然冲突, 则再次进行增量, 依此循环直到找到一个 Array 中的空位为止. 将来查找 K2 的时候先搜索 HashOf(K2) 一档, 发现不是 K2, 那么增量 d(K2) 继续搜索, 直到找到为止. 连续冲突次数越多, 搜索次数也越多, 效率越低.


put 和 get 的源码

	public synchronized V get(Object key) {
		Entry tab[] = table;
		int hash = key.hashCode();
		int index = (hash & 0x7FFFFFFF) % tab.length;
		for (Entry<K, V> e = tab[index]; e != null; e = e.next) {
			if ((e.hash == hash) && e.key.equals(key)) {
				return e.value;
			}
		}
		return null;
	}
	public synchronized V put(K key, V value) {
		// Make sure the value is not null
		if (value == null) {
			throw new NullPointerException();
		}

		// Makes sure the key is not already in the hashtable.
		Entry tab[] = table;
		int hash = key.hashCode();
		int index = (hash & 0x7FFFFFFF) % tab.length;
		for (Entry<K, V> e = tab[index]; e != null; e = e.next) {
			if ((e.hash == hash) && e.key.equals(key)) {
				V old = e.value;
				e.value = value;
				return old;
			}
		}

		modCount++;
		if (count >= threshold) {
			// Rehash the table if the threshold is exceeded
			rehash();

			tab = table;
			index = (hash & 0x7FFFFFFF) % tab.length;
		}

		// Creates the new entry.
		Entry<K, V> e = tab[index];
		tab[index] = new Entry<K, V>(hash, key, value, e);
		count++;
		return null;
	}

其中，这一句比较关键。

int index = (hash & 0x7FFFFFFF) % tab.length;

tab.length 就是容量。

更详细的，可以自行阅读一下源码。

评论

1 楼 zwhc 2010-08-06  

既然初始容量最好为质数，那么，贴一个质数的东东吧。

http://topic.csdn.net/t/20040821/22/3297408.html

代码主要来自于这里。做了一点修改：
1、直接指定开始值为终止值
2、输出到文件里。

package test;

import java.io.BufferedReader;
import java.io.FileOutputStream;
import java.io.IOException;
import java.io.InputStreamReader;

public class PrimeExplorer {
	public static void main(String[] args) throws IOException {
		int startValue;
		int endValue;
		int n;
		int sqrt;
		int divisor;
		int count;
		Prime head;
		Prime tail;
		Prime prime;
		boolean isPrime;
		BufferedReader in;

		in = new BufferedReader(new InputStreamReader(System.in));

		// Get input.
//		do {
//			try {
//				//System.out.print("From:   ");
//				startValue = Integer.parseInt(in.readLine());
//				//System.out.print("To:       ");
//				endValue = Integer.parseInt(in.readLine());
//				// Start from 11.
//				if (startValue < 11 || endValue <= startValue) {
//					continue;
//				} else {
//					break;
//				}
//			} catch (NumberFormatException e) {
//				continue;
//			}
//		} while (true);
		startValue = 11;
		endValue = 10000000;

		n = startValue;
		// Start from even.
		if (n % 2 == 0) {
			n++;
		}
		count = 0;

		// Prepare all prime numbers in 10 except 1.
		head = new Prime(5);
		head.next = new Prime(3);
		head.next.next = new Prime(7);
		prime = head;
		tail = head.next.next;

		// ========================================
		long startTime = System.currentTimeMillis();
		
		FileOutputStream fo = new FileOutputStream("prime.txt");
		fo.write(("2\r\n3\r\n5\r\n7\r\n").getBytes());

		for (isPrime = true; n < endValue; n += 2, prime = head, isPrime = true) {

			sqrt = (int) Math.sqrt(n) + 1;

			// Find prime number.
			for (divisor = prime.value; prime.next != null; prime = prime.next, divisor = prime.value) {
				if (n % divisor == 0) {
					isPrime = false;
					break;
				} else if (divisor > sqrt) {
					break;
				}
			}

			// Append this prime number to the list tail.
			if (isPrime) {
				count++;
				prime = tail;
				prime.next = new Prime(n);
				tail = prime.next;
				// TODO: Uncommont this for validating result.
				// System.out.println(n);
				fo.write((n+"\r\n").getBytes());
				//fo.write("/r/n".getBytes());
			}
		}

		System.out.println("Total:   " + count);
		long endTime = System.currentTimeMillis();
		System.out.println("cost:   " + (endTime - startTime));
		// ========================================
	}

	private static class Prime {
		public Prime next = null;
		public int value;

		public Prime(int value) {
			this.value = value;
		}
	}
}