ods/java/ods/LinearHashTable.java at master · gitpine/ods

1264 lines (1241 loc) · 19.1 KB

package ods;

import java.util.HashSet;

import java.util.Iterator;

import java.util.Random;

import java.util.Set;

* An implementation of linear probing. The hash method used is tabulation hashing.

* @author morin

* @param <T>

public class LinearHashTable<T> implements USet<T> {

protected static final int w = 32;

protected static final int r = 8;

Factory<T> f;

T[] t; // the table

* Special marker - used to show deleted nodes

int n; // the size

int d; // t.length = 2^d

int q; // number of non-null entries in t

* @param nil an object of class T that will never be

* stored in the table

@SuppressWarnings("unchecked")

public LinearHashTable(T nil) {

this.del = nil;

f = new Factory<T>((Class<T>)nil.getClass());

t = f.newArray(1<<d);

* Resize the backing array to have size 2^d

* Warning: 2^d should be much bigger than n

protected void resize() {

while ((1<<d) < 3*n) d++;

T[] told = t;

t = f.newArray(1<<d);

// insert everything from told

for (int k = 0; k < told.length; k++) {

if (told[k] != null && told[k] != del) {

int i = hash(told[k]);

while (t[i] != null)

i = (i == t.length-1) ? 0 : i + 1;

t[i] = told[k];

protected int hash(T x) {

int h = x.hashCode();

return (tab[0][h&0xff]

^ tab[1][(h>>>8)&0xff]

^ tab[2][(h>>>16)&0xff]

^ tab[3][(h>>>24)&0xff])

/* sample code

protected int idealHash(T x) {

return tab[x.hashCode() >>> w-d];

/* this code is broken - repeatedly adding and removing the same element gives a big chain

public boolean addSlow(T x) {

if (2*(q+1) > t.length) resize(); // max 50% occupancy

int i = hash(x);

while (t[i] != null) {

if (t[i] != del && x.equals(t[i])) return false;

i = (i == t.length-1) ? 0 : i + 1; // increment i

return true;

public boolean add(T x) {

if (find(x) != null) return false;

if (2*(q+1) > t.length) resize(); // max 50% occupancy

int i = hash(x);

while (t[i] != null && t[i] != del)

i = (i == t.length-1) ? 0 : i + 1; // increment i

if (t[i] == null) q++;

return true;

* A faster version of add(x)

public boolean add2(T x) {

if (2*(q+1) > t.length) resize(); // max 50% occupancy

int i = hash(x), j = -1;

while (t[i] != null) {

if (t[i] == del && j == -1) j = i;

if (t[i] != del && t[i].equals(x)) return false;

i = (i == t.length-1) ? 0 : i + 1; // increment i

t[j == -1 ? i : j] = x;

return true;

public T find(T x) {

int i = hash(x);

while (t[i] != null) {

if (t[i] != del && x.equals(t[i])) return t[i];

i = (i == t.length-1) ? 0 : i + 1; // increment i

return null;

public T remove(T x) {

int i = hash(x);

while (t[i] != null) {

if (y != del && x.equals(y)) {

if (8*n < t.length) resize(); // min 12.5% occupancy

i = (i == t.length-1) ? 0 : i + 1; // increment i

return null;

public int size() {

public void clear() {

t = f.newArray(1<<d);

public Iterator<T> iterator() {

class IT implements Iterator<T> {

int i, iprev;

public IT() {

while (i < t.length && (t[i] == null || t[i] == del)) i++;

public boolean hasNext() {

return i < t.length;

public T next() {

while (i < t.length && (t[i] == null || t[i] == del)) i++;

public void remove() {

t[iprev] = del;

return new IT();

* @param args

public static void main(String[] args) {

Random rand = new Random(1);

USet<Integer> lht = new LinearHashTable<Integer>(-1);

Set<Integer> s = new HashSet<Integer>();

int n = 1000000;

System.out.println("Adding");

for (int i = 0; i < n; i++) {

Integer x = rand.nextInt(n);

boolean rs = s.add(x);

boolean rlht = lht.add(x);

if (rs != rlht)

throw new RuntimeException("Aaaaaaaaaaaaaaaah!");

if (s.size() != lht.size()) {

System.out.println(s.size());

System.out.println(lht.size());

throw new RuntimeException("Bwaaaaaaaaaaaaaaah!");

System.out.println("Searching");

for (int i = 0; i < n; i++) {

Integer x = rand.nextInt(n);

boolean rs = s.contains(x);

boolean rlht = lht.find(x) != null;

if (rs != rlht)

throw new RuntimeException("Aaaaaaaaaaaaaaaah!");

if (s.size() != lht.size())

throw new RuntimeException("Bwaaaaaaaaaaaaaaah!");

System.out.println("Removing");

for (int i = 0; i < n; i++) {

Integer x = rand.nextInt(n);

boolean rs = s.remove(x);

boolean rlht = lht.remove(x) != null;

if (rs != rlht)

throw new RuntimeException("Aaaaaaaaaaaaaaaah!");

if (s.size() != lht.size())

throw new RuntimeException("Bwaaaaaaaaaaaaaaah!");

lht.clear();

* Table used by tabular hashing

protected static int[][] tab =

{{0x0069aeff,

0xcb54d5e5},

{0x116fc403,

0xc4152307},

{0xf07e5e34,

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

FilesExpand file tree

LinearHashTable.java

Latest commit

History

LinearHashTable.java

File metadata and controls