HashTable

1. 宣告


import java.util.Hashtable;

Hashtable ht = new Hashtable();

2. 使用


.    ht.put(key1, value1);

     value2 = ht.get(key2)

3. 注意 : Key 的 class 要定義 equals 和 hashcode

public boolean equals(Object that);

public int hashCode();

4. HashTable 實現

    不同於傳統 碰撞時跑第二次 hash function 找空位, 改用 link 直接串起來. 

5. Java Program (without expending hash table )

package neo.ds;

import java.io.*;

public class MyHashTable {

private MyEntryList[] table;

private float loadFactor;

private int threshold;

 

public MyHashTable(int initialCapacity, float loadFactor) {

if (initialCapacity < 0)

throw new IllegalArgumentException("Illegal Capacity: "+

                                         initialCapacity);

if (loadFactor <= 0 || Float.isNaN(loadFactor))

             throw new IllegalArgumentException("Illegal Load: "+loadFactor);

    

    if (initialCapacity==0)

         initialCapacity = 1;

    

    this.loadFactor = loadFactor;

    table = new MyEntryList[initialCapacity];

    threshold = (int)(initialCapacity * loadFactor);

    }

    

public MyHashTable(int initialCapacity) {

          this(initialCapacity, 0.75f);

}

public MyHashTable() {

         this(9973, 0.75f);

}

 

public synchronized V get(K key) {

 MyEntryList tab[] = table;

 int hash = key.hashCode();

 int index = (hash & 0x7FFFFFFF) % tab.length;

 

//  System.out.println("get(): key="+key+", hash="+hash+", index="+index);

 MyEntryList elist = tab[index];

 if (elist==null) return null;

 MyEntry e = elist.getEntryHead();

//  System.out.println("e="+e);

 while ( e != null) {

//  System.out.println("e.key="+e.key);

 if (e.key.equals(key)) return e.value;

 e = elist.getNextEntry();

 }

 

 return null;

}

 public synchronized void put(K key, V value) {

 int count;

 // Make sure the value is not null

 if (value == null) {

    throw new NullPointerException();

 }

 // Makes sure the key is not already in the hashtable.

 MyEntryList tab[] = table;

 int hash = key.hashCode();

 int index = (hash & 0x7FFFFFFF) % tab.length;

//  System.out.println("put(): key="+key+", hash="+hash+", index="+index);

 

 MyEntryList elist = tab[index];

 if (elist == null) {

 elist = new MyEntryList();

 tab[index] = elist;

 }

 

 elist.addEntry(new MyEntry(key, value));

// count 

 

// rehash

}  

/*

public static void main(String[] args){

        System.out.println("Test MyHashTable");

        

        MyHashTable ht = new MyHashTable();

        

        ht.put("Thousand", new Integer(1000));

        ht.put("Hundred", new Integer(100));

        ht.put("Ten", new Integer(10));

        

        Integer a = ht.get("Thousand");

        System.out.println("a="+a);

    }

*/

}