模拟HashSet底层实现

以你之姓@ 2024-02-18 21:12 39阅读 0赞

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

1、基本概念：

1）HashSet和HashMap唯一的不同之处在于，HashMap以键值对作为一个条目存储在散列表中，而HashSet则以元素的形式存储在散列表中；HashSet相当于HashMap的简化版。

2）MySet继承自java.lang.Iterable，实现了其方法，故MyHashSet中的元素是可以遍历的。

3）时间复杂度：clear()、iterator()、rehash()都是O(capacity)，而contains() 、 add()、remove()、isEmpty()、size()都是O(1)。

具体实现：

MySet接口：

package hash;
    
    public interface MySet<E> extends java.lang.Iterable<E> {
       /**清除所有元素*/
       public void clear();
       /**Return true if the element is in the set*/
       public boolean contains(E e);
       /**add a element to the set*/
       public boolean add(E e);
       /**Remove the element from the set*/
       public boolean remove(E e);
       /**set是否为空*/
       public boolean isEmpty();
       /**返回set大小*/
       public int size();
    }

实现：

package hash;
    
    import java.util.ArrayList;
    import java.util.Iterator;
    import java.util.LinkedList;
    
    public class MyHashSet<E> implements MySet<E>{
    	/**初始哈希表大小，必须是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;   
        
        /**hash table*/
        private LinkedList<E>[] table;
        
        /**使用默认容量和装载因子的构造函数*/
        public MyHashSet() {
    		this(DEFAULT_INITIAL_CAPACITY,DEFAULT_MAX_LOAD_FACTOR);
    	}
        
        /**指定初始容量*/
        public MyHashSet(int initialCapacity) {
        	this(initialCapacity,DEFAULT_MAX_LOAD_FACTOR);
        }
        
        /**指定初始容量及装载因子*/
        public MyHashSet(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;
    	}
    	
    
    	/**cleart the set*/
    	@Override
    	public void clear() {
    		size = 0;
    		removeElements();		
    	}
    	private void removeElements() {
    		for(int i = 0; i < capacity; i++) {
    			if(table[i] != null) {
    				table[i].clear();
    			}
    		}		
    	}
    	
    	/**是否包含指定元素*/
    	@Override
    	public boolean contains(E e) {
    		int bucketIndex = hash(e.hashCode());
    		if(table[bucketIndex] != null) {
    			LinkedList<E> bucket = table[bucketIndex];
    			for(E element : bucket) {
    				if(element.equals(e)) {
    					return true;
    				}
    			}
    		}
    		
    		return false;
    	}
    
    	/**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);
    	}	
    	
    	/**add a element to the set*/
    	@Override
    	public boolean add(E e) {
    		if(contains(e))
    			return false;
    		
    		if(size + 1 > capacity * loadFactorThreshold) {
    			if(capacity == MAXIMUM_CAPACITY)
    				throw new RuntimeException("Exceeding maximum capacity");
    			
    			rehash();
    		}
    		
    		int bucketIndex = hash(e.hashCode());
    		
    		//Create a linked list for the bucket if not already created
    		if(table[bucketIndex] == null) {
    			table[bucketIndex] = new LinkedList<>();
    		}
    		
    		table[bucketIndex].add(e);
    		size++;
    		
    		return true;
    	}
    
    	/**再散列*/
    	private void rehash() {
    		ArrayList<E> list = setToList();
    		capacity <<= 1;
    		table = new LinkedList[capacity];
    		size = 0;
    		
    		for (E e : list) {
    			add(e);
    		}
    	}
    
    	/**Copy elements in the hash set to an array list*/
    	private ArrayList<E> setToList() {
    		ArrayList<E> list = new ArrayList<>();
    		
    		for(int i = 0; i < capacity; i++) {
    			if(table[i] != null) {
    				for (E e : table[i]) {
    					list.add(e);
    				}
    			}
    		}
    		
    		return list;
    	}
    
    	/**Remove the element from the set*/
    	@Override
    	public boolean remove(E e) {
    		if(!contains(e))
    			return false;
    		
    		int bucketIndex = hash(e.hashCode());
    		
    		//Remove the element from the bucket
    		if(table[bucketIndex] != null) {
    			LinkedList<E> bucket = table[bucketIndex];
    			for (E element : bucket) {
    				bucket.remove(element);
    				break;
    			}
    		}
    		
    		size--;
    		
    		return true;
    	}
    
    	@Override
    	public boolean isEmpty() {
    		return size == 0;
    	}
    
    	@Override
    	public int size() {
    		return size;
    	}
    
    
    	@Override
    	public Iterator<E> iterator() {
    		return new MyHashSetIterator(this);
    	}	
    	
    	/**Inner class for iterator*/
    	private class MyHashSetIterator implements java.util.Iterator<E>{
            private ArrayList<E> list;
            private int current = 0;
            private MyHashSet<E> set;
            
            public MyHashSetIterator(MyHashSet<E> set) {
            	this.set = set;
    			list = setToList();
    		}
    		
    		@Override
    		public boolean hasNext() {
    			
    			if(current < list.size())
    				return true;
    			
    			return false;
    		}
    
    		@Override
    		public E next() {
    			return list.get(current++);
    		}
    
    		@Override
    		public void remove() {
    			set.remove(list.get(current));
    			list.remove(current);
    		}
    		
    	}
    	
    	
    	@Override
    	public String toString() {
    		ArrayList<E> list = setToList();
    		StringBuilder builder = new StringBuilder("[");
    		
    		for(int i = 0; i < list.size() - 1; i++) {
    			builder.append(list.get(i) + ", ");
    		}
    		
    		if(list.size() == 0)
    			builder.append("]");
    		else {
    			builder.append(list.get(list.size() - 1) + "]");
    		}
    		
    		return builder.toString();
    	}
    	
    	
    }

测试：

package hash;
    
    public class TestMyHashSet {
    
    	public static void main(String[] args) {
           MySet<String> set = new MyHashSet<>();
           set.add("Smith");
           set.add("Anderson");
           set.add("Lewis");
           set.add("Cook");
           set.add("Smith");       
           
           System.out.println("Element in set: " + set);
           System.out.println("Number of elements in set: " + set.size());
           System.out.println("Is Smith in set? " + set.contains("Smith"));
           
           set.remove("Smith");
           System.out.print("Names in set in uppercase are ");
           for (String s : set) {
    		System.out.print(s.toUpperCase() + " ");
    	}
           
           set.clear();
           System.out.println("\nElement in set: " + set);
    	}
    
    }
    
    
    /**
    Element in set: [Anderson, Smith, Lewis, Cook]
    Number of elements in set: 4
    Is Smith in set? true
    Names in set in uppercase are ANDERSON LEWIS COOK 
    Element in set: []
     * */