package hash; import java.util.Arrays; // tables de hachage class Bucket { final String element; Bucket next; Bucket(String element, Bucket next) { this.element = element; this.next = next; } static boolean contains(Bucket b, String s) { for (; b != null; b = b.next) if (b.element.equals(s)) return true; return false; } static Bucket remove(Bucket b, String s) { if (b == null) return null; if (b.element.equals(s)) return b.next; b.next = remove(b.next, s); return b; } static String toString(Bucket b) { StringBuffer sb = new StringBuffer(""); for (; b != null; b = b.next) sb.append(b.element + ", "); return sb.toString(); } } public class HashTable implements intf.Set<String> { private int size; // total number of elements private Bucket[] buckets; final private static int M = 17; public HashTable() { this.size = 0; this.buckets = new Bucket[M]; } private int hash(String s) { int h = 0; for (int i = 0; i < s.length(); i++) h = s.charAt(i) + 19 * h; return (h & 0x7fffffff) % M; } public void add(String s) { int i = hash(s); if (Bucket.contains(this.buckets[i], s)) return; this.buckets[i] = new Bucket(s, this.buckets[i]); this.size++; } public boolean contains(String s) { int i = hash(s); return Bucket.contains(this.buckets[i], s); } public String toString() { StringBuffer sb = new StringBuffer("["); for (Bucket b : this.buckets) sb.append(Bucket.toString(b)); sb.append("]"); return sb.toString(); } public boolean isEmpty() { return this.size == 0; } public int size() { return this.size; } public void remove(String s) { int i = hash(s); if (!Bucket.contains(this.buckets[i], s)) return; this.buckets[i] = Bucket.remove(this.buckets[i], s); this.size--; } @Override public void clear() { Arrays.fill(this.buckets, null); this.size = 0; } }