Skip to content

Instantly share code, notes, and snippets.

@wrightak
Created February 19, 2021 07:01
Show Gist options
  • Save wrightak/dcaa6575ba56b8e2b88924123faf36c7 to your computer and use it in GitHub Desktop.
Save wrightak/dcaa6575ba56b8e2b88924123faf36c7 to your computer and use it in GitHub Desktop.
Simple HashSet implementation
import java.util.Objects;
public class Set {
private final Object[][] elements;
private int size = 0;
public Set(int capacity) {
elements = new Object[capacity][];
}
public Set() {
this(32);
}
public boolean isEmpty() {
return size == 0;
}
public void add(Object element) {
final int index = indexOf(element);
if (elements[index] == null) {
elements[index] = new Object[] { element };
} else {
final Object[] existingChain = elements[index];
if (indexInChain(existingChain, element) > -1) {
return;
}
final Object[] newChain = new Object[existingChain.length + 1];
System.arraycopy(existingChain, 0, newChain, 0, existingChain.length);
newChain[existingChain.length] = element;
elements[index] = newChain;
}
size++;
}
public void remove(Object element) {
final int index = indexOf(element);
if (elements[index] != null) {
final Object[] chain = elements[index];
final int indexInChain = indexInChain(chain, element);
if (indexInChain == -1) {
return;
}
final Object[] newChain = new Object[chain.length - 1];
System.arraycopy(chain, 0, newChain, 0, indexInChain);
System.arraycopy(chain, indexInChain + 1, newChain, indexInChain, chain.length - indexInChain - 1);
elements[index] = newChain;
size--;
}
}
public int size() {
return size;
}
public boolean contains(Object element) {
final int index = indexOf(element);
if (elements[index] != null) {
final Object[] chain = elements[index];
return indexInChain(chain, element) > -1;
}
return false;
}
static int indexInChain(Object[] chain, Object element) {
for (int i = 0; i < chain.length; i++) {
if (Objects.equals(chain[i], element)) {
return i;
}
}
return -1;
}
int indexOf(Object element) {
return element.hashCode() % elements.length;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment