HashSet with chaining

OpenHashMap.java

import java.math.BigInteger;
import java.util.Arrays;


public class OpenHashMap {
    class Entry {
    	String key;
    	String value;
    	
    	public Entry(String key, String value) {
    		this.key = key;
    		this.value = value;
    	}
    }
    
    class Node {
    	private final static int DEFAULT_CAPACITY = 4;
    	Entry entry[] = new Entry[DEFAULT_CAPACITY];
		int curSize = 0;
		int maxSize = DEFAULT_CAPACITY;
		
		String put(String key, String value) {
			if (curSize + 1 >= maxSize) {
				entry = Arrays.copyOf(entry, maxSize *= 2);
			}
			int next = next(key);
			String prev = null;
			if (next < curSize) {
				prev = entry[next].value = value;
			} else {
				entry[curSize++] = new Entry(key, value);
			}
			
			return prev;
		}
		
		int next(String key) {
		    for (int i = 0; i < curSize; ++i) {
		    	if (entry[i].key.equals(key)) {
		    		return i;
		    	}
		    }
		    return curSize;
		}
		
		String remove(String key) {
			for (int i = 0; i < curSize; ++i) {
				if (entry[i].key.equals(key)) {
					String found = entry[i].value;
					for (int j = i + 1; j < curSize; ++j) {
						entry[j - 1] = entry[j];
					}
					entry[curSize--] = null;
					return found;
				}
				
			}
			
			return null;
		}
		
		String get(String key) {
			for (int i = 0; i < curSize; ++i) {
				if (entry[i].key.equals(key)) {
					return entry[i].value;
				}
			}
			return null;
		}
		
    }
    
	public final static double DEFAULT_LOAD_FACTOR = 0.75;
	public final static int DEFAULT_CAPACITY = nextPrime(32);
	public final static double DEFAULT_INCREMENT_FACTOR = 1.75;
	private int maxSize;
	private double loadFactor;
	private Node buckets[];
	private int curSize;

	private static int nextPrime(int num) {
		BigInteger bigNum = new BigInteger(String.valueOf(num));
		return bigNum.nextProbablePrime().intValue();
	}

	public OpenHashMap(int maxSize, double loadFactor) {
		this.maxSize = maxSize;
		this.loadFactor = loadFactor;
		buckets = new Node[maxSize];
		curSize = 0;
	}

	public OpenHashMap() {
		this(DEFAULT_CAPACITY, DEFAULT_LOAD_FACTOR);
	}

	private int hash(String snum) {
		int hash = 0;
		
		for (char c : snum.toCharArray()) { hash = hash * 7 + c; }
		 
		hash %= maxSize;
		return hash < 0 ? -hash : hash;
	}

	public boolean put(String key, String value) {
		if ((long) (curSize * (1.0 + loadFactor)) >= maxSize) {

			int oldMaxSize = maxSize;
			maxSize = nextPrime((int) (maxSize * DEFAULT_INCREMENT_FACTOR));
			// System.out.println("Rehashing **************" + maxSize);
			Node newNodes[] = new Node[maxSize];
			int newCurSize = 0;
			for (int i = 0; i < oldMaxSize; ++i) {
				if (buckets[i] != null) {
					for (int j = 0; j < buckets[i].curSize; ++j) {
						Entry entry = buckets[i].entry[j];
						if (addNode(entry.key, entry.value, newNodes)) {
							++newCurSize;
						}
					}
				}
			}
			buckets = null;
			curSize = newCurSize;
			buckets = newNodes;
		}
		boolean added = addNode(key, value, buckets);
		if (added) {
			++curSize;
		}
		return added;
	}

	private boolean addNode(String key, String value, Node nodes[]) {
		int hash = hash(key);
		if (nodes[hash] == null) {
			nodes[hash] = new Node();
		}
		return nodes[hash].put(key, value) == null;
	}

	public String remove(String key) {
		int hash = hash(key);
		String removed = null;
		
		if (buckets[hash] != null) {
			removed = buckets[hash].remove(key);
			if (removed != null) {
				--curSize;
			}
		}
		return removed;
	}
	
	public String get(String key) {
		int hash = hash(key);
		String value = null;
		if (buckets[hash] != null) { 
			value = buckets[hash].get(key);
		}
		return value;
	}

	public boolean containsKey(String key) {
		int hash = hash(key);
		return buckets[hash] != null && buckets[hash].get(key) != null;
	}

	public int size() {
		return curSize;
	}

	public void clear() {
		curSize = 0;
		Arrays.fill(buckets, null);
	}
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		OpenHashMap map = new OpenHashMap();
		for (int i = 0; i < 100; ++i) {
			map.put(i + "", i + "");
		}
		map.put(1 + "", 100 + "");
		System.out.println(map.remove(1 + ""));
		System.out.println(map.size());
		System.out.println(map.containsKey(50 + ""));
		map.put(1 + "", 2555 + "");
		System.out.println(map.get(1 + ""));
	}

}

OpenHashSet.java

import java.math.BigInteger;
import java.util.Arrays;

/*
 * Simple Hashing for Strings
 */

public class OpenHashSet {
  class Node {
		private final static int DEFAULT_CAPACITY = 4;
		String val[] = new String[DEFAULT_CAPACITY];
		int curSize = 0;
		int maxSize = DEFAULT_CAPACITY;

		public boolean add(String key) {
			if (contains(key)) {
				return false;
			}

			if (curSize + 1 >= maxSize) {
				val = Arrays.copyOf(val, maxSize *= 2);
			}
			val[curSize++] = key;
			return true;
		}

		public boolean contains(String key) {
			for (int i = 0; i < curSize; ++i) {
				if (val[i].equals(key)) {
					return true;
				}
			}
			return false;
		}

		public boolean remove(String key) {
			for (int i = 0; i < curSize; ++i) {
				if (key.equals(val[i])) {
					for (int j = i + 1; j < curSize; ++j) {
						val[j - 1] = val[j];
					}
					val[--curSize] = null;
					return true;
				}
			}
			return false;
		}
	}

	public final static double DEFAULT_LOAD_FACTOR = 0.75;
	public final static int DEFAULT_CAPACITY = nextPrime(32);
	public final static double DEFAULT_INCREMENT_FACTOR = 1.75;
	private int maxSize;
	private double loadFactor;
	private Node buckets[];
	private int curSize;

	private static int nextPrime(int num) {
		BigInteger bigNum = new BigInteger(String.valueOf(num));
		return bigNum.nextProbablePrime().intValue();
	}

	public OpenHashSet(int maxSize, double loadFactor) {
		this.maxSize = maxSize;
		this.loadFactor = loadFactor;
		buckets = new Node[maxSize];
		curSize = 0;
	}

	public OpenHashSet() {
		this(DEFAULT_CAPACITY, DEFAULT_LOAD_FACTOR);
	}

	private int hash(String snum) {
		int hash = 0;
		
		for (char c : snum.toCharArray()) { hash = hash * 7 + c; }
		 
		hash %= maxSize;
		return hash < 0 ? -hash : hash;
	}

	public boolean add(String key) {
		if ((long) (curSize * (1.0 + loadFactor)) >= maxSize) {

			int oldMaxSize = maxSize;
			maxSize = nextPrime((int) (maxSize * DEFAULT_INCREMENT_FACTOR));
			// System.out.println("Rehashing **************" + maxSize);
			Node newNodes[] = new Node[maxSize];
			int newCurSize = 0;
			for (int i = 0; i < oldMaxSize; ++i) {
				if (buckets[i] != null) {
					for (int j = 0; j < buckets[i].curSize; ++j) {
						if (addNode(buckets[i].val[j], newNodes)) {
							++newCurSize;
						}
					}
				}
			}
			buckets = null;
			curSize = newCurSize;
			buckets = newNodes;
		}
		boolean added = addNode(key, buckets);
		if (added) {
			++curSize;
		}
		return added;
	}

	private boolean addNode(String key, Node nodes[]) {
		int hash = hash(key);
		if (nodes[hash] == null) {
			nodes[hash] = new Node();
		}
		return nodes[hash].add(key);
	}

	public boolean remove(String key) {
		int hash = hash(key);
		boolean removed = buckets[hash] != null && buckets[hash].remove(key);
		if (removed) {
			--curSize;
		}
		return removed;
	}

	public boolean contains(String key) {
		int hash = hash(key);
		return buckets[hash] != null && buckets[hash].contains(key);
	}

	public int size() {
		return curSize;
	}

	public void clear() {
		curSize = 0;
		Arrays.fill(buckets, null);
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		OpenHashSet set = new OpenHashSet();
		long atStart = System.currentTimeMillis();
		 
		 atStart = System.currentTimeMillis(); 
		 
		 atStart = System.currentTimeMillis();
		 for (int c = 1; c <= 1000000; ++c) {
			set.add(c + "");
			set.remove((c) + "");
			// System.out.println("Added " + c + " Cap:" + set.maxSize);
		 }
		set.remove(1 + "");
		System.out.println(set.contains(1 + ""));
		System.out.println(set.add(1 + ""));
		set.remove(111111  + "");
		
		System.out.println("Time required : "
				+ (System.currentTimeMillis() - atStart) / 1000.0);
		System.out.println(set.size());
		
 

		/*
		 * for (int c = 1; c <= 100; ++c) { int num = new Random().nextInt(201);
		 * System.out.println(num + " " + set.contains(num + "")); }
		 */
	}

}