使用哈希实现映射
- WBOY原创
- 2024-07-28 07:43:13513浏览
地图可以使用散列来实现。现在您了解了哈希的概念。您知道如何设计良好的哈希函数以将键映射到哈希表中的索引，如何使用负载因子衡量性能，以及如何增加表大小和重新哈希以维持性能。本节演示如何使用单独的链接来实现映射。
我们设计自定义的 Map 接口来镜像 java.util.Map 并将接口命名为 MyMap 和一个具体类 MyHashMap ，如下图所示。
如何实现MyHashMap？如果您使用 ArrayList 并将新条目存储在列表末尾，则搜索时间将为 O(n)。如果使用二叉树实现 MyHashMap，如果树平衡良好，则搜索时间将为 O(log n)。尽管如此，您可以使用哈希来实现 MyHashMap 以获得 O(1) 时间的搜索算法。下面的代码显示了MyMap界面。
package demo;
public interface MyMap<K, V> {
/** Remove all of the entries from this map */
public void clear();
/** Return true if the specified key is in the map */
public boolean containsKey(K key);
/** Return true if this map contains the specified value */
public boolean containsValue(V value);
/** Return a set of entries in the map */
public java.util.Set<Entry<K, V>> entrySet();
/** Return the value that matches the specified key */
public V get(K key);
/** Return true if this map doesn't contain any entries */
public boolean isEmpty();
/** Return a set consisting of the keys in this map */
public java.util.Set<K> keySet();
/** Add an entry (key, value) into the map */
public V put(K key, V value);
/** Remove an entry for the specified key */
public void remove(K key);
/** Return the number of mappings in this map */
public int size();
/** Return a set consisting of the values in this map */
public java.util.Set<V> values();
/** Define an inner class for Entry */
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;
}
@Override
public String toString() {
return "[" + key + ", " + value + "]";
}
}
}
下面的代码使用单独的链接实现MyHashMap。
package demo;
import java.util.LinkedList;
public class MyHashMap<K, V> implements MyMap<K, V> {
// Define the default hash-table size. Must be a power of 2
private static int DEFAULT_INITIAL_CAPACITY = 4;
// Define the maximum hash-table size. 1 << 30 is same as 2^30
private static int MAXIMUM_CAPACITY = 1 << 30;
// Current hash-table capacity. Capacity is a power of 2
private int capacity;
// Define default load factor
private static float DEFAULT_MAX_LOAD_FACTOR = 0.75f;
// Specify a load factor used in the hash table
private float loadFactorThreshold;
// The number of entries in the map
private int size = 0;
// Hash table is an array with each cell being a linked list
LinkedList<MyMap.Entry<K, V>>[] table;
/** Construct a map with the default capacity and load factor */
public MyHashMap() {
this(DEFAULT_INITIAL_CAPACITY, DEFAULT_MAX_LOAD_FACTOR);
}
/** Construct a map with the specified initial capacity and
* default load factor */
public MyHashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_MAX_LOAD_FACTOR);
}
/** Construct a map with the specified initial capacity
* and 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 /** 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[i] != null) {
LinkedList<Entry<K ,V>> bucket = table[i];
for(Entry<K, V> entry: bucket)
if(entry.getValue().equals(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[i] != null) {
LinkedList<Entry<K, V>> bucket = table[i];
for(Entry<K, V> entry: bucket)
set.add(entry);
}
}
return set;
}
@Override /** Return the value that matches the specified key */
public V get(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))
return entry.getValue();
}
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<K>();
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 /** Add an entry (key, value) into the map */
public V put(K key, V value) {
if(get(key) != null) { // The key is already in the map
int bucketIndex = hash(key.hashCode());
LinkedList<Entry<K, V>> bucket = table[bucketIndex];
for(Entry<K, V> entry: bucket)
if(entry.getKey().equals(key)) {
V oldValue = entry.getValue();
// Replace old value with new value
entry.value = value;
// Return the old value for the key
return oldValue;
}
}
// Check load factor
if(size >= capacity * loadFactorThreshold) {
if(capacity == MAXIMUM_CAPACITY)
throw new RuntimeException("Exceeding maximum capacity");
rehash();
}
int bucketIndex = hash(key.hashCode());
// Create a linked list for the bucket if not already created
if(table[bucketIndex] == null) {
table[bucketIndex] = new LinkedList<Entry<K, V>>();
}
// Add a new entry (key, value) to hashTable[index]
table[bucketIndex].add(new MyMap.Entry<K, V>(key, value));
size++; // Increase size
return value;
}
@Override /** Remove the entries for the specified key */
public void remove(K key) {
int bucketIndex = hash(key.hashCode());
// Remove the first entry that matches the key from a bucket
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--; // Decrease size
break; // Remove just one entry that matches the key
}
}
}
@Override /** Return the number of entries in this map */
public int size() {
return size;
}
@Override /** Return a set consisting of the 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[i] != null) {
LinkedList<Entry<K, V>> bucket = table[i];
for(Entry<K, V> entry: bucket)
set.add(entry.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; // Same as capacity *= 2. <= is more efficient
}
return capacity;
}
/** Remove all entries from each bucket */
private void removeEntries() {
for(int i = 0; i < capacity; i++) {
if(table[i] != null) {
table[i].clear();
}
}
}
/** Rehash the map */
private void rehash() {
java.util.Set<Entry<K, V>> set = entrySet(); // Get entries
capacity <<= 1; // Same as capacity *= 2. <= is more efficient
table = new LinkedList[capacity]; // Create a new hash table
size = 0; // Reset size to 0
for(Entry<K, V> entry: set) {
put(entry.getKey(), entry.getValue()); // Store to new table
}
}
@Override /** Return a string representation for this map */
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();
}
}
MyHashMap 类使用单独的链接实现 MyMap 接口。确定哈希表大小和负载因子的参数在类中定义。默认初始容量为 4（第 5 行），最大容量为 2^30（第 8 行）。当前的哈希表
容量被设计为 2 的幂值（第 11 行）。默认负载因子阈值是 0.75f（第 14 行）。您可以在构建地图时指定自定义负载因子阈值。自定义负载因子阈值存储在 loadFactorThreshold（第 17 行）中。数据字段 size 表示映射中的条目数（第 20 行）。哈希表是一个数组。数组中的每个单元格都是一个链表（第 23 行）。
提供了三个构造函数来构造地图。您可以使用无参数构造函数构造一个具有默认容量和负载因子阈值的默认映射（第 26-28 行），一个具有指定容量和默认负载因子阈值的映射（第 32-34 行），以及一个具有指定容量和负载系数阈值的映射（第 38-46 行）。
clear 方法从映射中删除所有条目（第 49-52 行）。它调用 removeEntries()，删除存储桶中的所有条目（第 221-227 行）。 removeEntries() 方法需要 O(capacity) 时间来清除表中的所有条目。
containsKey(key) 方法通过调用 get 方法检查指定的键是否在映射中（第 55-60 行）。由于 get 方法需要 O(1) 时间，因此 containsKey(key) 方法需要 O(1) 时间。
containsValue(value) 方法检查值是否在地图中（第 63-74 行）。此方法需要 O(容量 + 大小) 时间。它实际上是 O(容量)，因为容量为 7 大小。
entrySet() 方法返回一个包含映射中所有条目的集合（第 77-90 行）。此方法需要 O(capacity) 时间。
get(key) 方法返回具有指定键的第一个条目的值（第 93-103 行）。此方法需要 O(1) 时间。
如果地图为空，isEmpty() 方法只会返回 true（第 106-108 行）。此方法需要 O(1) 时间。
keySet() 方法将映射中的所有键作为一个集合返回。该方法从每个存储桶中查找键并将它们添加到一个集合中（第 111-123 行）。此方法需要 O(capacity) 时间。
put(key, value) 方法在映射中添加一个新条目。该方法首先测试键是否已在映射中（第 127 行），如果是，则找到该条目并用该键条目中的新值替换旧值（第 134 行），然后返回旧值（第 136 行）。如果映射中的键是新的，则会在映射中创建新条目（第 156 行）。在插入新条目之前，该方法检查大小是否超过负载因子阈值（第 141 行）。如果是这样，程序会调用 rehash() （第 145 行）来增加容量并将条目存储到新的更大的哈希表中。
rehash()方法首先复制集合中的所有条目（第231行），将容量加倍（第232行），创建一个新的哈希表（第233行），并将大小重置为0（第 234 行）。然后该方法将条目复制到新的哈希表中（第 236-238 行）。 rehash 方法需要 O(capacity) 时间。如果不执行重新哈希，则 put 方法需要 O(1) 时间来添加新条目。
remove(key) 方法删除映射中具有指定键的条目（第 164-177 行）。此方法需要 O(1) 时间。
size() 方法仅返回地图的大小（第 180-182 行）。此方法需要 O(1) 时间。
values() 方法返回映射中的所有值。该方法检查所有存储桶中的每个条目并将其添加到一个集合中（第 185-197 行）。此方法需要 O(capacity) 时间。
hash() 方法调用 supplementalHash 以确保散列均匀分布以生成散列表的索引（第 200-208 行）。此方法需要 O(1) 时间。
下表总结了MyHashMap中方法的时间复杂度。
由于重新哈希不会经常发生，因此 put 方法的时间复杂度为 O(1)。请注意，clear、entrySet、keySet、values 和 rehash 方法的复杂性取决于 容量，因此为了避免这些方法性能不佳，您应该仔细选择初始容量。
下面的代码给出了一个使用MyHashMap.
的测试程序
程序使用 MyHashMap 创建一个映射（第 7 行），并向映射添加五个条目（第 8-12 行）。第 5 行添加键 Smith，值为 30，第 9 行添加 Smith，值为 65。后一个值替换前一个值。该地图实际上只有四个条目。该程序显示映射中的条目（第 14 行），获取键的值（第 16 行），检查映射是否包含该键（第 18 行）和值（第 19 行），删除带有键 Smith（第 21 行），并重新显示地图中的条目（第 22 行）。最后，程序清除地图（第 24 行）并显示一个空地图（第 25 行）。
以上是使用哈希实现映射的详细内容。更多信息请关注PHP中文网其他相关文章！