HashSet的实现

2017/04/01 Algorithm

tips: Hast Set的Java实现

HashSet的实现

public class HashSet {
	class Entry{
		int value;
		Entry next;
		
		public Entry(int value){
			this.value = value;
		}
	}
	
	private int size;
	private int capacity;
	private double loadFactor;
	
	private Entry[] arr;
	
	public HashSet(int capacity, double loadFactor){
		this.size = 0;
		this.capacity = capacity;
		this.loadFactor = loadFactor;
		
		this.arr = new Entry[capacity];
	}
	
	private int getIndexOf(int value){
		Integer i = Integer.valueOf(value);
		
		return i.hashCode() % capacity;
	}
	
	private void reHash(){
		Entry[] oldArr = arr;
		
		size = 0;
		capacity = (int)(capacity * 1.5);
		arr = new Entry[capacity];
		
		for(Entry entry : oldArr){
			Entry p = entry;
			while(p != null){
				put(p.value);
				p = p.next;
			}
		}
	}
	
	public boolean put(int value){
		int index = getIndexOf(value);
		if(arr[index] == null){
			arr[index] = new Entry(value);
			size++;
			if(size > capacity * loadFactor){
				reHash();
			}
			return true;
		}else{
			Entry p = arr[index];
			while(p.next != null){
				if(p.value == value){
					return false;
				}
				p = p.next;
			}
			
			if(p.value == value){
				return false;
			}
			
			p.next = new Entry(value);
			size++;
			if(size > capacity * loadFactor){
				reHash();
			}
			
			return true;
		}
	}
	
	public boolean remove(int value){
		int index = getIndexOf(value);
		if(arr[index] == null){
			return false;
		}
		
		Entry p = arr[index];
		if(p.value == value){
			arr[index] = null;
			size--;
			return true;
		}
		
		Entry q = arr[index];
		p = p.next;
		while(p != null){
			if(p.value == value){
				q.next = p.next;
				size--;
				return true;
			}
			
			q = q.next;
			p = p.next;
		}
		
		return false;
	}
	
	public int size(){
		return size;
	}

}

Search

    Table of Contents