模拟HashMap底层实现

╰+哭是因爲堅強的太久メ 2024-02-18 21:12 80阅读 0赞

GitHub源码地址（https://github.com/BradenLei/MyHashMap）

1、概念：

1）散列：使用一个散列函数，将一个键映射到一个索引上。

2）散列函数：将键映射到散列表中的索引上的函数称为散列函数。

3）冲突：当两个键映射到散列表中的同一个索引上，冲突发生

a：使用开发地址法解决处理冲突（线性探测、二次探测法、再哈希法）

b：使用链地址法处理冲突：将具有同样的散列索引的条目都放在一个位置，每个位置使用一个桶来放置多个条目；通常使用LinkedList来实现一个桶。

4）装填因子和再散列：装填因子用来衡量一个散列表有多满。再散列：如果装填因子溢出，则增加散列表的大小，并重新装载条目到一个新的更大的散列表中。

2、使用散列实现映射表：用一个哈希表存储，每个下表对应可能有多个条目，因此每个下表相当于对应一个桶，装了多个条目，而桶这里采用LinkedList实现。

存储原理图：

![70][]

实现代码：

接口定义：

package hash;
    
    public interface MyMap<K,V> {
        /**Remove all of the entries from this map*/
        public void clear();
        /**是否存在特定的键值*/
    	public boolean containKey(K key);
    	/**是否存在特定的值*/
    	public boolean containValue(V value);
    	/**Return a set of entries in the map*/
    	public java.util.Set<Entry<K, V>> entrySet();
    	/**返回特定的键对应的值*/
    	public V get(K key);
    	/**是否为空*/
    	public boolean isEmpty();
    	/**返回键值集合*/
    	public java.util.Set<K> keySet();
    	/**Add a entry(key,value) into the map*/
    	public V put(K key,V value);
    	/**Remove the number for the specified key*/
    	public void remove(K key);
    	/**返回Entry个数*/
    	public int size();
    	/**返回map中的所有的值集合*/
    	public java.util.Set<V> values();
    
    	/**定义内部类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 + "]";
    		}
    	}
    }

接口实现：

package hash;
    
    import java.util.LinkedList;
    import java.util.Set;
    
    public class MyHashMap<K,V> implements MyMap<K, V> {
    	/**初始哈希表大小，必须是2的幂次方*/
        private static int DEFAULT_INITIAL_CAPACITY = 4;
    	/**默认最大哈希表容量,2^30*/
        private static int MAXIMUM_CAPACITY = 1 << 30;
        /**哈希表容量*/
        private int capacity;
        /**默认装载因子*/
        private static float DEFAULT_MAX_LOAD_FACTOR = 0.75f;
        /**指出特定的装载因子*/
        private float loadFactorThreshold;
        /**entry数量*/
        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];
        }
        
        /**Return a power of 2 for initialCapacity*/
    	private int trimToPowerOf2(int initialCapacity) {
    		int capacity = 1;
    		while(capacity < initialCapacity) {
    			capacity <<= 1;
    		}
    		
    		return capacity;
    	}
    
    	/**Remove all of the entries from this map*/
    	@Override
    	public void clear() {
    		size = 0;
    		removeEntries();
    	}
    
    	private void removeEntries() {
    		for(int i = 0; i < capacity; i++) {
    			if(table[i] != null) {
    				table[i].clear();
    			}
    		}
    	}
    
    	/**Return true if the specified key is in the map*/
    	@Override
    	public boolean containKey(K key) {
    		if(get(key) != null)
    			return true;
    		else 
    		    return false;
    	}
    
    	/**Return true if this map contains the value*/
    	@Override
    	public boolean containValue(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;
    	}
    
    	/**Return a set of entries in the map*/
    	@Override
    	public 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[i] != null) {
    				LinkedList<Entry<K, V>> bucket = table[i];
    				for(Entry<K, V> entry : bucket)
    					set.add(entry);
    			}
    		}
    		return set;
    	}
    
    	/**Return the value that mathces the specified key*/
    	@Override
    	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;
    	}
    
    	/**hash fucntion*/
    	private int hash(int hashCode) {
    		return supplementalHash(hashCode) & (capacity - 1);
    	}
    
    	/**确保hash值均匀分布*/
    	private int supplementalHash(int h) {
    		h ^= (h >>> 20) ^ (h >>> 12);
    		return h ^ (h >>> 7) ^ (h >>> 4);
    	}
    
    	/**Return a set consisting of the keys in this map*/
    	@Override
    	public Set<K> keySet() {
    		java.util.Set<K> 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.getKey());
    				}
    			}
    		}
    		return set;
    	}
    
    	/**Add an entry(key,value) into the map*/ 
    	@Override
    	public V put(K key, V value) {
    		if(get(key) != null) {
    			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();
    					entry.value = value;
    					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<>();
    		}
    		
    		table[bucketIndex].add(new MyMap.Entry<K, V>(key, value));
    		
    		size++;
    		return value;
    	}
    
    	/**Rehash the map*/
    	private void rehash() {
    		java.util.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());
    		}
    		
    	}
    
    	/**Remove the entries for the specified key*/
    	@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;
    				}
    			}
    		}
    	}
    
    	/**Return the number of entries in this map*/
    	@Override
    	public int size() {
    		return size;
    	}
    
    	/**Return a set consisting of the valuse in this map*/
    	@Override
    	public 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 null;
    	}
    
    	/**Return true if this map contains no entries*/
    	@Override
    	public boolean isEmpty() {		
    		return size == 0;
    	}
    	
    	@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();
    	}
    
    }

测试代码：

package hash;
    
    public class TestMyhashMap {
    
    	public static void main(String[] args) {
             MyHashMap<String, Integer> map = new MyHashMap<>();
             map.put("Smith", 30);
             map.put("Anderson", 31);
             map.put("Lewis", 29);
             map.put("Cook", 29);
             map.put("Smith", 65);
             
             System.out.println("Entries in map: "+ map);
             
             System.out.println("The age for Lewis is " + map.get("Lewis"));
             
             System.out.println("Is Smith in the map?" + map.containKey("Smith"));
             
             System.out.println("Is age 33 in the map?" + map.containValue(33));
             
             map.remove("Smith");
             System.out.println("Entries in map: "+ map);
             
             map.clear();
             System.out.println("Entries in map: " + map);
             
    	}
    
    }
    
    /**
    Entries in map: [[Anderson, 31][Smith, 65][Lewis, 29][Cook, 29]]
    The age for Lewis is 29
    Is Smith in the map?true
    Is age 33 in the map?false
    Entries in map: [[Anderson, 31][Lewis, 29][Cook, 29]]
    Entries in map: []
     */

3、效率分析：

1）clear方法删除映射表中所有条目，时间复杂度O(capacity)

2）containsKey(key)方法，由于get方法耗费O(1)时间，故containsKey(key)也耗费O(1)时间。

3）containsValue(value)，O(capacity + size) -----> capacity > size ，故为O(capacity)

4）keySet() ： O(capacity)

5）remove()：O(1)

散列非常高效，使用散列将耗费O(1)时间来查找、插入以及删除一个元素

[70]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/68c07c45638b48678aed04d0c0b08cf2.png