散列表

发表于 | 分类于 | 阅读次数:
字数统计: 4.8k | 阅读时长 ≈ 27

在一个良好平衡的查找树中，可以在O(logn)时间内找到一个元素。 使用散列来实现一个映射表或集合，从而在O(1)时间内查找、插入和删除一个元素。

HashMap

java.util.HashMap

public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable

HashMap和Hashtable有什么区别？

  • HashMap是Hashtable的轻量级实现（非线程安全的实现），都实现了Map接口，主要区别是HashMap允许key为null(但只允许一条null)，而后者不行。
  • HashMap把contains方法去掉，改为containsKey()和containsValue()。 Hashtable继承自Dictionary，而HashMap实现了Map接口，继承自AbstractMap。
  • Hashtable使用Enumeration遍历，而HashMap使用Iterator遍历。
  • 使用的hash/rehash算法几乎一致，性能差别不大
  • Hashtable的hash数组默认大小是11,增加方式是2*old + 1。 HashMap中，hash数组默认大小是16，一定是2的指数。

一般在不需要并发的时候使用HashMap，并发的时候使用锁粒度更细的ConcurrentHashMap。
迭代HashMap使用了快速失败机制，fail-fast，是Java集合的一种错误检测机制。当多个线程对集合进行结构上的改变操作时，就有可能产生fail-fast事件。假如线程1和线程2，当线程1通过iterator遍历集合A中的元素时，如果线程2修改了集合A的结构（删除、增加新元素），程序就会抛出ConcurrentModificationException异常，从而产生fail-fast事件。

遍历HashMap的四种方法：
keySet需要首先把key转换成itaretor，然后根据key在map中取出value，需要两个操作，而entrySet只一次操作就把key和value都取到entry中来，效率更高。foreach和itaretor是等价的。

  1. foreach map.entrySet()
foreach map.entrySet()
1
2
3
4
5
public static void traversal(Map<String, String> map) {
	for (Entry<String, String> entry : map.entrySet()) {
		System.out.print(entry.getKey() + ", " + entry.getValue());
	}
}
  1. 显示调用map.entrySet集合迭代器
显示调用map.entrySet集合迭代器 
1
2
3
4
5
6
7
8
public static void traversal(Map<String, Integer> map) {
	Iterator<Map.Entry<String, Integer>> iterator =
		 map.entrySet().iterator();
	while (iterator.hasNext()) {
		Map.Entry<String, Integer> entry = iterator.next();
		System.out.println(entry.getKey() + ", " + entry.getValue());
	}
}
  1. foreach map.keySet(), 再调用get方法
    本方法多调用一次get，效率会降低，只适合只遍历key的情况。
foreach map.keySet(), 再调用get方法
1
2
3
4
5
public static void traversal(Map<String, String> map) {
	for (String key : map.keySet()) {
		System.out.println(key + ", " + map.get(key));
	}
}
  1. foreach map.entrySet(), 再临时变量保存map.entrySet()
foreach map.entrySet(), 再临时变量保存map.entrySet()
1
2
3
4
5
6
public static void traversal(Map<String, String> map) {
	Set<Entry<String, String>> entrySet = map.entrySet();
	for (Entry<String, String> enty : entrySet) {
		System.out.println(entry.getKey() + ", " + entry.getValue());
	}
}

散列函数和散列码

折叠法

byte、short、int、char类型的搜索键，简单地转换为int。
long类型的散列码： hashCode = (int)(key ^ (key >> 32));
double类型： long bits = Double.doubleToLongBits(key);
int hashCode = (int)(bits ^ (bits >> 32));

除余法(压缩)

假设散列表的索引处于0~N-1 之间。设N为2的幂值。

h(hashCode) = hashCode % N;
h(hashCode) = hashCode & (N - 1);
为了保证散列码是均匀分布的，java.util.HashMap采用了补充的散列函数与主散列函数一起使用。

字符串类型的散列码

(…((s0 * b) + s1)b + s2)b + … + sn-2)b + sn-1
在String中，b取值31，来计算上述多项式，以达到最小化冲突，其中si = s.charAt(i)。

除此之外，还有平方取中法，数字分析法等等。

使用链地址法处理冲突

当两个键映射到散列表中的同一个索引上时，冲突发生。链地址法将具有同样的散列索引的条目都放在同一个位置，而不是寻找一个新位置。链地址法的每个位置使用一个桶来放置多个条目。
可以使用数组，ArrayList或LinkedList来实现一个桶。
使用LinkedListl来实现一个映射表。 此处实现与jdk中的实现不同，只是为了演示理解。

MyMap接口

MyMap接口 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
import java.util.Set;

public interface MyMap<K, V> {
//	删除映射表中所有条目
	void clear();
//	映射表是否包含键的条目
	boolean containsKey(K key);
//	如果映射表将一个或多个键映射到指定的值 返回true
	boolean containsValue(V value);
//	返回包含该映射表中所有条目的集合
	Set<Entry<K, V>> entrySet();
//	指定键对应的值
	V get(K key);
//	是否包含映射条目
	boolean isEmpty();
//	映射表所有键的集合
	Set<K> keySet();
//	将一个映射置于映射表中
	V put(K key, V value);
//	移除指定键的条目
	void remove(K key);
//	映射条目数
	int size();
//	映射表值的集合
	Set<V> values();
//	映射条目的内部静态类
	public static class Entry<K, V> {
		K key;
		V value;
		
		public Entry(K key, V value) {
			this.key = key;
			this.value = value;
		}
		public K getKey() {
			return key;
		}
		public V getValue() {
			return value;
		}
		public String toString() {
			return "[" + key + ", " + value + "]";
		}
	}
}

MyHashMap类的实现

MyHashMap类链地址法处理冲突的实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
import java.util.*;
public class MyHashMap<K ,V> implements MyMap<K, V> {
	private static int DEFAULT_INITIAL_CAPACITY = 4;
	private static int MAXIMUM_CAPACITY = 1 << 30;	
	private int capacity;
	private static float  DEFAULT_MAX_LOAD_FACTOR = 0.75f;	
	private float loadFactorThreshold;
	//映射表条目数，只有执行一次方法put(key, value)后，size才会增加一次
	private int size = 0; 
	
	LinkedList<MyMap.Entry<K, V>>[] table; 
	//散列表是一个数组，数组中的每个单元是一个链表

	public MyHashMap() {
		this(DEFAULT_INITIAL_CAPACITY, DEFAULT_MAX_LOAD_FACTOR);
	}
	public MyHashMap(int initialCapacity) {
		this(initialCapacity, DEFAULT_MAX_LOAD_FACTOR);
	}
	public MyHashMap(int initialCapacity, float loadFactorThreshold) {
		if (initialCapacity > MAXIMUM_CAPACITY) {
			this.capacity = MAXIMUM_CAPACITY;
		} else {
			this.capacity = trimToPowerOf2(initialCapacity);
		}
		this.loadFactorThreshold = loadFactorThreshold;
		table = new LinkedList[capacity];
	}

	@Override
	public void clear() {
		size = 0;
		removeEntries();
	}
	private void removeEntries() { //耗费时间为O(capacity)
		for (int i = 0; i < capacity; i++) {
			if (table[i] != null) {
				table[i].clear();
			}
		}
	}

	@Override
	public boolean containsKey(K key) { //耗费时间也为O(1)
		if (get(key) != null) {
			return true;
		} else {
			return false;
		}
	}
	@Override
	public boolean containsValue(V value) { 
		LinkedList<Entry<K, V>> bucket;
		for (int i = 0; i < capacity; i++）{
			if (table[i] != null) {
				bucket = table[i];
				for (Entry<K, V> entry : bucket) {
					if (entry.getValue().equals(value))
						return true;
				}
			}
		}
	}

	@Override
	public Set<Entry<K, V>> entrySet() {
		Set<MyMap.Entry<K, V>> set = new HashSet<>();
		LinkedList<Entry<K, V>> bucket;
		for (int i = 0; i < capacity; i++) {
			if (table[i] != null) {
				bucket = table[i];
				for (Entry<K ,V> entry : bucket)
					set.add(entry);
			}
		}
		return set;
	}

	@Override
	public V get(K key) { //耗费O(1)的时间
		int bucketIndex = hash(key.hashCode());
		LinkedList<Entry<K, V>> bucket;
		if (table[bucketIndex] != null) {
			bucket = table[bucketIndex];
			for (Entry<K, V> entry : bucket) {
				if (entry.getKey().equals(key))
					return entry.getValue();
			}
		}
		return null;
	}

	@Override
	public boolean isEmpty() {
		return size == 0;
	}
	
	@Override
	public Set<K> keySet() {
		Set<K> set = new HashSet<>();
		for (int i = 0; i < capacity; i++) {
			if (table[i] != null) {
				LinkedList<Entry<K, V>> bucket = table[i];
				for (Entry<K, V> entry: bucket) {
					set.add(entry.getKey());
				}
			}
		}
		return set;
	}
	@Override
	public V put(K key, V value) {
		if (get(key) != null) {
			int bucketIndex = hash(key.hashCode());
			LinkedList<Entry<K, V>> entry = table[bucketIndex];
			for (Entry<K, V> entry : bucket) {
				if (entry.getKey().equals(key)) {
					V oldValue = entry.getValue();
					entry.value = value;
					return oldValue;
				}
			}
		}
		if (size >= capacity * loadFactorThreshold) {
			if (capacity == MAXIMUM_CAPACITY)
				throw new RuntimeException("Exceeding maximum capacity");
			rehash();
		}
		int bucketIndex = hash(key.hashCode());
		if (table[bucketIndex] == null) {
			table[bucketIndex] = new LinkedList<Entry<K, V>>();
		}
		table[bucketIndex].add(new MyMap.Enty<K, V>(key, value));
		size++;
		return value;
	}
	@Override
	public void remove(K key) {
		int bucketIndex = hash(key.hashCode());
		
		if (table[bucketIndex] != null) {
			LinkedList<Entry<K, V>> bucket = table[bucketIndex];
			for (Entry<K, V> entry : bucket) {
				if (entry.getKey().equals(key)) {
					bucket.remove(entry);
					size--;
					break;
				}
			}
		}
	}	

	@Override
	public int size() {
		return size;
	}

	@Override
	public Set<V> values() {
		Set<V> set = new HashSet<>();
		for (int i = 0; i < capacity; i++) {
			if (table[i] != null) {
				LinkedList<Entry<K, V>> bucket = table[i];
				for (Entry<K, V> entry : bucket) {
					set.add(entry.getValue());
				}
			}
		}
		return set;
	}
	
	private int hash(int hashCode) {
		return supplementalHash(hashCode) & (capacity - 1);
	}
	
	private static int supplementalHash(int h) {
		h ^= (h >>> 20) ^ (h >>> 12);
		return h ^ (h >>> 7) ^ (h >>> 4);
	}
	
	private int trimToPowerOf2(int initialCapacity) {
		int capacity = 1;
		while (capacity < initialCapacity) {
			capacity <<= 1;
		}
		return capacity;
	}
	private void rehash() {
		Set<Entry<K, V>> set = entrySet();
		capacity <<= 1;
		
		table = new LinkedList[capacity];
		size = 0;
		
		for (Entry<K, V> entry : set) {
			put(entry.getKey(), entry.getValue());
		}
	}
	
	@Override
	public String toString() {
		StringBuilder builder = new StringBuilder();
		for (int i = 0; i < capacity; i++) {
			if (table[i] != null && table[i].size() > 0) {
				for (Entry<K, V> entry: table[i]) {
					builder.append(entry);
				}
			}
		}
		builder.append("]");
		return builder.toString();
	}
}

使用开放地址法处理冲突

开放地址法（open addressing）是在冲突发生时，在散列表中找到一个开放位置的过程。

线性探测法

按照顺序找到下一个可用的位置，如果冲突发生在hashTable[k % N]，则检查hashTable[(k+1) % N]，依次类推。
查找时，依次检查k，k+1，…，直到达到一个空单元，或者找到。
缺点：会形成一次簇（cluster），从而降低查找时间。

线性探测法处理冲突
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
import java.util.ArrayList;

public class MyHashMap<K, V> implements MyMap<K, V> {
	
	private static int DEFAULT_INITIAL_CAPACITY = 4;	
	private static int  MAXIMUM_CAPACITY = 1 << 30;	
	private int capacity;
	
	private static float DEFAULT_MAX_LOAD_FACTOR = 0.5f;	
	private float loadFactorThreshold;
	
	private int size = 0;	
	ArrayList<MyMap.Entry<K, V>> table;
	
	public MyHashMap() {
		this(DEFAULT_INITIAL_CAPACITY, DEFAULT_MAX_LOAD_FACTOR);
	}
	public MyHashMap(int initialCapacity) {
		this(initialCapacity, DEFAULT_MAX_LOAD_FACTOR);
	}
	public MyHashMap(int initialCapacity, float loadFactorThreshold) {
		if (initialCapacity > MAXIMUM_CAPACITY)
			this.capacity = MAXIMUM_CAPACITY;
		else
			this.capacity = trimToPowerOf2(initialCapacity);

		this.loadFactorThreshold = loadFactorThreshold;
		table = new ArrayList<>();
		for (int i = 0; i < capacity; i++)
			table.add(null);
	}

	@Override 
	public void clear() {
		size = 0;
		removeEntries();
	}
	@Override 
	public boolean containsKey(K key) {
		if (get(key) != null)
			return true;
		else
			return false;
	}
	@Override 
	public boolean containsValue(V value) {
		for (int i = 0; i < capacity; i++) {
			if (table.get(i) != null && table.get(i).getValue() == value)
				return true;
		}

		return false;
	}

	@Override 
	public java.util.Set<MyMap.Entry<K,V>> entrySet() {
		java.util.Set<MyMap.Entry<K, V>> set = 
			new java.util.HashSet<>();

		for (int i = 0; i < capacity; i++) {
			if (table.get(i) != null) {
				set.add(table.get(i));
			}
		}

		return set;
	}

	@Override 
	public V get(K key) {
		int index = hash(key.hashCode());

		while(table.get(index) != null) {
			if (table.get(index).getKey().equals(key)) {
					return table.get(index).getValue();
			}
			index++;
			index %= capacity;
		}

		return null;
	}

	@Override 
	public boolean isEmpty() {
		return size == 0;
	}

	@Override 
	public java.util.Set<K> keySet() {
		java.util.Set<K> set = new java.util.HashSet<K>();

		for (int i = 0; i < capacity; i++) {
			if (table.get(i) != null)
				set.add(table.get(i).getKey());
		}

		return set;
	}

	@Override /** Add an entry (key, value) into the map */
	public V put(K key, V value) {
		int index = hash(key.hashCode());

		while (table.get(index) != null) {
			// The key is already in the map
			if (table.get(index).getKey().equals(key)) {
				Entry<K, V> entry = table.get(index);
				V oldvalue = entry.getValue();
				// Replace old value with new value
				entry.value = value;
				table.set(index, entry);
				// Return the old value for the key
				return oldvalue;
			}
			// Collision check if the next index is available
			index++; 
			index %= capacity;
		}
		// Check load factor
		if (size >= capacity * loadFactorThreshold) {
			if (capacity == MAXIMUM_CAPACITY)
				throw new RuntimeException("Exceeding maximum capacity");
			rehash();
		}
		// Add a new entry (key, value) to hashtable
		table.set(index, new MyMap.Entry<K, V>(key, value));
		size++; // Increase size
		return value;
	} 

	@Override /** Remove the entry for the specified key */
	public void remove(K key) {
		int index = hash(key.hashCode());
		
		// Remove the entry that matches the key
		while (table != null) {
			if (table.get(index).getKey().equals(key)) {
				table.remove(index);
				size--; // Decrease size
				break; // Remove just one entry that matches the key
			}
			index++;
			index %= capacity;
		}
	}


	@Override /** Return the number of entries in this map */
	public int size() {
		return size;
	}

	@Override /** Return a set consisting of values in this map */
	public java.util.Set<V> values() {
		java.util.Set<V> set = new java.util.HashSet<>();

		for (int i = 0; i < capacity; i++) {
			if (table.get(i) != null)
				set.add(table.get(i).getValue());
		}

		return set;
	}

	/** Hash function */
	private int hash(int hashCode) {
		return supplementalHash(hashCode) & (capacity - 1);
	}

	/** Ensure the hashing is evenly distributed */
	private static int supplementalHash(int h) {
		h ^= (h >>> 20) ^ (h >>> 12);
		return h ^ (h >>> 7) ^ (h >>> 4);
	}

	/** Return a power of 2 for initialCapacity */
	private int trimToPowerOf2(int initialCapacity) {
		int capacity = 1;
		while (capacity < initialCapacity) {
			capacity <<= 1;
		}

		return capacity;
	}
	
	private void removeEntries() {
		table.clear();
	}

	/** Rehash the map */
	private void rehash() {
		java.util.Set<Entry<K, V>> set = entrySet();
		capacity <<= 1; // Same as capacity *= 2. <= is more efficient	
		size = 0; // Reset size to 0
		table.clear(); // Clear the hash table
		for (int i = 0; i < capacity; i++)
			table.add(null);

		for (Entry<K, V> entry : set) {
			put(entry.getKey(), entry.getValue());
		}
	}

	@Override /** Return a string repesentation for this map */
	public String toString() {
		StringBuilder builder = new StringBuilder("[");
		for (Entry<K, V> entry: table) {
			if (entry != null && table.size() > 0)
				builder.append(entry);
		}
		builder.append("]");
		return builder.toString();
	}
}

二次探测法

二次探测法从索引 (k + j*j) % N位置的单元开始审查。

二次探测法处理冲突
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
import java.util.ArrayList;

public class MyHashMap<K, V> implements MyMap<K, V> {
	private static int DEFAULT_INITIAL_CAPACITY = 4;
	private static int MAXIMUM_CAPACITY = 1 << 30;
	private int capacity;
	private static float DEFAULT_MAX_LOAD_FACTOR = 0.5f;
	private float loadFactorThreshold;
	private int size = 0;
	ArrayList<MyMap.Entry<K, V>> table;

	public MyHashMap() {
		this(DEFAULT_INITIAL_CAPACITY, DEFAULT_MAX_LOAD_FACTOR);
	}
	public MyHashMap(int initialCapacity) {
		this(initialCapacity, DEFAULT_MAX_LOAD_FACTOR);
	}
	public MyHashMap(int initialCapacity, float loadFactorThreshold) {
		if (initialCapacity > MAXIMUM_CAPACITY)
			this.capacity = MAXIMUM_CAPACITY;
		else
			this.capacity = trimToPowerOf2(initialCapacity);

		this.loadFactorThreshold = loadFactorThreshold;
		table = new ArrayList<>();
		for (int i = 0; i < capacity; i++) {
			table.add(null);
		}
	}

	@Override /** Remove all of the entries from this map */
	public void clear() {
		size = 0;
		removeEntries();
	}
	@Override /** Return true if the specified key is in the map */
	public boolean containsKey(K key) {
		if (get(key) != null)
			return true;
		else
			return false;
	}
	@Override /** Return true if this map contains the value */
	public boolean containsValue(V value) {
		for (int i = 0; i < capacity; i++) {
			if (table.get(i) != null && table.get(i).getValue() == value)
				return true;
		}

		return false;
	}
	@Override /** Return a set of entries in the map */
	public java.util.Set<MyMap.Entry<K, V>> entrySet() {
		java.util.Set<MyMap.Entry<K, V>> set = 
			new java.util.HashSet<>();

		for (int i = 0; i < capacity; i++) {
			if (table.get(i) != null) {
				set.add(table.get(i));
			}
		}
		return set;
	}

	@Override /** Return the value that matches the specified key */
	public V get(K key) {
		int index = hash(key.hashCode());
		int j = 0;

		while (table.get(index) != null) {
			if (table.get(index).getKey().equals(key)) {
				return table.get(index).getValue();
			}
			index += Math.pow(j++, 2);
			index %= capacity;
		}

		return null;
	}

	@Override /** Return true if this map contains no entries */
	public boolean isEmpty() {
		return size == 0;
	}

	@Override /** Return a set consisting of the keys in this map */
	public java.util.Set<K> keySet() {
		java.util.Set<K> set = new java.util.HashSet<>();

		for (int i = 0; i < capacity; i++) {
			if (table.get(i) != null) {
				set.add(table.get(i).getKey());
			}
		}
		return set;
	}

	@Override /** Add an entry (key, value) into the map */
	public V put(K key, V value) {
		int index = hash(key.hashCode());
		int j = 0;

		while (table.get(index) != null) {
			// The key is already in the map
			if (table.get(index).getKey().equals(key)) {
				Entry<K, V> entry = table.get(index);
				V oldValue = entry.getValue();
				// Replace old value with new value
				entry.value = value;
				table.set(index, entry);
				// Return the old value for the key
				return oldValue;
			}
			index += Math.pow(j++, 2);
			index %= capacity;
		}

		// Check load factor
		if (size >= capacity * loadFactorThreshold) {
			if (capacity == MAXIMUM_CAPACITY)
				throw new RuntimeException("Exceeding maximum capacity");
			rehash();
		}

		// Add a new entry(key, value) to hashtable
		table.set(index, new MyMap.Entry<K, V>(key, value));
		size++; // Increase size
		return value;
	}

	@Override /** Remove the entry for the specified key */
	public void remove(K key) {
		int index = hash(key.hashCode());
		int j = 0;
		// Remove the first entry that matches the key
		while (table.get(index) != null) {
			if (table.get(index).getKey().equals(key)) {
				table.remove(index);
				size--; // Decrease size
				break; // Remove just one entry that matches key
			}
			index += Math.pow(j++, 2);
			index %= capacity;
		}
	}

	@Override /** Return the number of entries in this map */
	public int size() {
		return size;
	}

	@Override /** Return a set consisting of values in this map */
	public java.util.Set<V> values() {
		java.util.Set<V> set = new java.util.HashSet<>();

		for (int i = 0; i < capacity; i++) {
			if (table.get(i) != null)
				set.add(table.get(i).getValue());
		}

		return set;
	}
	/** Hash function */
	private int hash(int hashCode) {
		return supplementalHash(hashCode) & (capacity - 1);
	}

	/** Ensure the hashing is evenly distributed */
	private static int supplementalHash(int h) {
		h ^= (h >>> 20) ^ (h >>> 12);
		return h ^ (h >>> 7) ^ (h >>> 4);
	}

	/** Return a power of 2 for initialCapacity */
	private int trimToPowerOf2(int initialCapacity) {
		int capacity = 1;
		while (capacity < initialCapacity) {
			capacity <<= 1;
		}
		return capacity;
	}

	/** Remove all entries from map */
	private void removeEntries() {
		table.clear();
	}

	/** Rehash the map */
	private void rehash() {
		java.util.Set<Entry<K, V>> set = entrySet();
		capacity <<= 1; // Same as capacity *= 2. <= is more efficient
		size = 0;
		table.clear();
		for (int i = 0; i < capacity; i++) 
			table.add(null);

		for (Entry<K, V> entry : set) {
			put(entry.getKey(), entry.getValue());
		}
	}

	@Override /** Return a string repersentation for this map */
	public String toString() {
		StringBuilder builder = new StringBuilder("[");

		for (Entry<K, V> entry: table) {
			if (entry != null && table.size() > 0)
				builder.append(entry);
		}

		builder.append("]");
		return builder.toString();
	}
}

再哈希法

再哈希法处理冲突
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
import java.util.ArrayList;

public class MyHashMap<K, V> implements MyMap<K, V> {
	private static int DEFAULT_INITIAL_CAPACITY = 4;
	private static int MAMIMUM_CAPACITY = 1 << 30;
	private int capacity;
	private static float DEFAULT_MAX_LOAD_FACTOR = 0.5f;
	private float loadFactorThreshold;
	private int size = 0;
	private ArrayList<MyMap.Entry<K, V>> table;
	public MyHashMap() {
		this(DEFAULT_INITIAL_CAPACITY, DEFAULT_MAX_LOAD_FACTOR);
	}
	public MyHashMap(int initialCapacity) {
		this(initialCapacity, DEFAULT_MAX_LOAD_FACTOR);
	}
	public MyHashMap(int initialCapacity, float loadFactorThreshold) {
		if (initialCapacity > MAMIMUM_CAPACITY)
			this.capacity = MAMIMUM_CAPACITY;
		else
			this.capacity = trimToPowerOf2(initialCapacity);

		this.loadFactorThreshold = loadFactorThreshold;
		table = new ArrayList<>();
		for (int i = 0; i < capacity; i++) {
			table.add(null);
		}
	}

	@Override
	public void clear() {
		size = 0;
		removeEntries();
	}

	@Override 
	public boolean containsKey(K key) {
		if (get(key) != null)
			return true;
		else
			return false;
	}

	@Override 
	public boolean containsValue(V value) {
		for (int i = 0; i < capacity; i++) {
			if (table.get(i) != null && 
				 table.get(i).getValue() == value)
				return true;
		}
		return false;
	}

	@Override 
	public java.util.Set<Entry<K, V>> entrySet() {
		java.util.Set<Entry<K, V>> set = new java.util.HashSet<>();
		for (int i = 0; i < capacity; i++) {
			if (table.get(i) != null) {
				set.add(table.get(i));
			}
		}
		return set;
	}

	@Override 
	public V get(K key) {
		int hash1 = hash(key.hashCode());
		int index = hash1;
		int j = 0;

		while (table.get(index) != null) {
			if (table.get(index).getKey().equals(key)) {
				return table.get(index).getValue();
			}
			// Secondary hash: (k + j * h'(key)) % N
			index = hash1 + j++ * hash2(hash1); 
			index %= capacity;
		}

		return null;
	}

	@Override /** Return true if this map contains no entries */
	public boolean isEmpty() {
		return size == 0;
	}

	@Override /** Return a set consisting of the keys in this map */
	public java.util.Set<K> keySet() {
		java.util.Set<K> set = new java.util.HashSet<>();

		for (int i = 0; i < capacity; i++) {
			if (table.get(i) != null)
				set.add(table.get(i).getKey());
		}

		return set;
	}

	@Override /** Add an entry (key, value) into the map */
	public V put(K key, V value) {
		int hash1 = hash(key.hashCode());
		int index = hash1;
		int j = 0;

		while (table.get(index) != null) {
			// The key is already in the map
			if (table.get(index).getKey().equals(key)) {
				Entry<K, V> entry = table.get(index);
				V oldValue = entry.getValue();
				// Replace old value with new value
				entry.value = value;
				table.set(index, entry);
				// Return the old value for the key
				return oldValue;
			}

			// Secondary hash: (k + j * h'(key)) % N
			index = hash1 + j++ * hash2(hash1); 
			index %= capacity;
		}

		// Check load factor
		if (size >= capacity * loadFactorThreshold) {
			if (capacity == MAMIMUM_CAPACITY)
				throw new RuntimeException("Exceeding maximum capacity");
			rehash();
		}

		// Add a new entry(key, value) to hashtable
		table.set(index, new MyMap.Entry<K, V>(key, value));

		size++;
		return value;
	}

	@Override /** Remove the entry for the specified key */
	public void remove(K key) {
		int hash1 = hash(key.hashCode());
		int index = hash1;
		int j = 0;

		// Remove the first entry that matched the key
		while (table.get(index) != null) {
			if (table.get(index).getKey().equals(key)) {
				table.remove(index);
				size--; // Decrease size
				break; // Remove just one entry that matches the key
			}

			// Secondary hash: (k + j * h'(key)) % N
			index = hash1 + j++ * hash2(hash1); 
			index %= capacity;
		}
	}

	@Override /** Return the number of entries in this map */
	public int size() {
		return size;
	}

	@Override /** Return a set consisting of values in this map */
	public java.util.Set<V> values() {
		java.util.Set<V> set = new java.util.HashSet<>();

		for (int i = 0; i < capacity; i++) {
			if (table.get(i) != null)
				set.add(table.get(i).getValue());
		}
		return set;
	}

	/** Hash function */
	private int hash(int hashCode) {
		return supplementalHash(hashCode) & (capacity - 1);
	}

	/** Ensure the hashing is evenly distributed */
	private static int supplementalHash(int h) {
		h ^= (h >>> 20) ^ (h >>> 12);
		return h ^ (h >>> 7) ^ (h >>> 4);
	}

	/** Secondary hash function */
	private int hash2(int hash) {
		return (7 - hash) & (7 - 1);
	}

	/** Return a power of 2 for initialCapacity */
	private int trimToPowerOf2(int initialCapacity) {
		int capacity = 1;
		while (capacity < initialCapacity) {
			capacity <<= 1;
		}
		return capacity;
	}

	/** Remove all entries from map */
	private void removeEntries() {
		table.clear();
	}

	/** Rehash the map */
	private void rehash() {
		java.util.Set<Entry<K, V>> set = entrySet();
		capacity <<= 1; // Same as capacity *= 2. <= is more efficient
		size = 0; // Reset size
		table.clear();
		for (int i = 0; i < capacity; i++) 
			table.add(null);
		
		for (Entry<K, V> entry : set) {
			put(entry.getKey(), entry.getValue());
		}
	}

	@Override /** Return a string repersentation of this map */
	public String toString() {
		StringBuilder builder = new StringBuilder("[");
		for (Entry<K, V> entry : table) {
			if (entry != null && table.size() > 0) {
				builder.append(entry);
			}
		}
		builder.append("]");
		return builder.toString();
	}
}
0%