wrote in an hour, went through several changes, maybe there’s some inconsistent/bad code, point it out for me if so.
it’s a ‘hashset’. it’s pretty good. has add, remove, contains, clear, size, and iterator, let me know if you need anything else added
[i][b]it’s not really a set though, since i skipped duplicate checking to gain speed. it would be trivial to add it however, and usually i don’t have a case where i am working with duplicate objects… (well actually I’ve never had a case with this, having an unordered collection was the important bit for me) and that’s why i decided not to include
don’t use negative hashes.[/b][/i]
/* DO WHAT THE F(U)CK YOU WANT TO PUBLIC LICENSE
* Version 2, December 2004
*
* Copyright (C) 2004 Sam Hocevar <sam@hocevar.net>
*
* Everyone is permitted to copy and distribute verbatim or modified
* copies of this license document, and changing it is allowed as long
* as the name is changed.
*
* DO WHAT THE F(U)CK YOU WANT TO PUBLIC LICENSE
* TERMS AND CONDITIONS FOR COPYING, DISTRIBUTION AND MODIFICATION
*
* 0. You just DO WHAT THE F(U)CK YOU WANT TO.
*/
import java.lang.reflect.Array;
import java.util.Iterator;
public class HashStruct<T> {
public HashStruct() {
this(1024);
}
@SuppressWarnings("unchecked")
public HashStruct(int estimatedMaxElements) {
elements = (Node[]) Array.newInstance(Node.class, estimatedMaxElements);
}
private Node[] elements;
private int size = 0;
public final boolean contains(T object) {
if (size == 0)
return false;
Node node = elements[object.hashCode() % elements.length];
if (node == null)
return false;
while (node.value != object) {
node = node.next;
if (node == null)
return false;
}
return true;
}
public final int size() {
return size;
}
public final void add(T object) {
int n = object.hashCode() % elements.length;
Node node = elements[n];
size++;
if (node == null) {
elements[n] = new Node(object);
return;
}
Node temp = new Node(object);
temp.next = node;
elements[n] = temp;
}
@SuppressWarnings("unchecked")
public final void clear() {
size = 0;
elements = (Node[]) Array.newInstance(Node.class, elements.length);
}
public final void remove(T object) {
int n = object.hashCode() % elements.length;
Node node = elements[n];
if (node == null)
return;
if (node.next == null) {
elements[n] = null;
size--;
return;
}
Node previous = null;
while (node.value != object) {
previous = node;
node = node.next;
if (node == null)
return;
}
if (previous != null)
previous.next = node.next;
else
elements[n] = node.next;
size--;
}
public final Iterator<T> iterator() {
return new HashStructIterator();
}
private final class Node {
public Node(T value) {
this.value = value;
}
public final T value;
public Node next;
}
private final class HashStructIterator implements Iterator<T> {
public HashStructIterator() {
initialSize = size;
if (initialSize != 0)
for (int i = 0; i < elements.length; i++)
if (elements[i] != null) {
pos = i;
current = elements[i];
return;
}
pos = elements.length;
}
private final int initialSize;
private int pos;
private int read;
private Node current;
private Node last;
@Override
public final boolean hasNext() {
if (!seek())
return false;
return pos != elements.length;
}
@Override
public final T next() {
if (!seek())
return null;
read++;
T next = current.value;
last = current;
current = current.next;
return next;
}
@Override
public final void remove() {
if (last == null || pos == elements.length)
throw new IllegalStateException("no element to remove!");
size--;
if (current == null) {
elements[pos] = null;
return;
}
last.next = current.next;
}
private final boolean seek() {
if (pos == elements.length)
return false;
if (read == initialSize) {
pos = elements.length;
return false;
}
if (current == null) {
for (int i = pos + 1; i < elements.length; i++)
if (elements[i] != null) {
pos = i;
current = elements[i];
return true;
}
pos = elements.length;
return false;
}
return true;
}
}
}
add = O(1)
remove = best case O(1), worst case O(n)
contains = best case O(1), worst case O(n)
iterator = O(n)
(best case is no collisions, worst case is ONLY having collisions