Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
HashSet with chaining
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 + ""));
}
}
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 + "")); }
*/
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.