Created
February 19, 2021 07:01
-
-
Save wrightak/dcaa6575ba56b8e2b88924123faf36c7 to your computer and use it in GitHub Desktop.
Simple HashSet implementation
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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