模仿st_table写的StTable类

    读ruby hacking guide，其中专门辟了一个章节介绍了st.c中的st_table，这个数据结构也就是类似java中的HashMap，基本原理是利用数组存储，数组的每一个元素是一个单向链表，链表中再存储具体的元素，如下图所示的结构

   ruby中利用这个结构来存储对象变量、类方法、常量、全局变量等信息，在c ruby中，方法、变量都是用一个整型作为键值来存储在st_table中，因此这个数据结构对于以整性为键的map类型来说速度非常不错（我没有测试内存的占用情况）。
源码如下：

java 代码

//接口，用于定义hash函数
//HashFunction.java
public interface HashFunction<T> {
   public int hash(T key);
}

链表元素类：

java 代码

public class StTableEntry<T, V> {
    protected int hash; //hash值

    protected T key;   //键

    protected V value; //存储值

    protected StTableEntry<T, V> next; //下一节点

    public StTableEntry() {

    }

    public StTableEntry(int hash, T key, V value, StTableEntry<T, V> next) {
        super();
        this.hash = hash;
        this.key = key;
        this.value = value;
        this.next = next;
    }

    public int getHash() {
        return hash;
    }

    public void setHash(int hash) {
        this.hash = hash;
    }

    public T getKey() {
        return key;
    }

    public void setKey(T key) {
        this.key = key;
    }

    public StTableEntry<T, V> getNext() {
        return next;
    }

    public void setNext(StTableEntry<T, V> next) {
        this.next = next;
    }

    public V getValue() {
        return value;
    }

    public void setValue(V value) {
        this.value = value;
    }

}

完整的StTable实现,没有实现remove，有兴趣的话自己实现一下：

java 代码

public final class StTable<T, V> {
    private HashFunction<T> hashFunction;

    private int num_bins;

    int num_entries;

    StTableEntry<T, V>[] bins;

    public static int DEFAULT_SIZE = 10;

    private static int DEFAULT_MAX_DENSITY = 5;

    private static int DEFAULT_MIN_SIZE = 8;

    private static long primes[] = { 8 + 3, 16 + 3, 32 + 5, 64 + 3, 128 + 3,
            256 + 27, 512 + 9, 1024 + 9, 2048 + 5, 4096 + 3, 8192 + 27,
            16384 + 43, 32768 + 3, 65536 + 45, 131072 + 29, 262144 + 3,
            524288 + 21, 1048576 + 7, 2097152 + 17, 4194304 + 15, 8388608 + 9,
            16777216 + 43, 33554432 + 35, 67108864 + 15, 134217728 + 29,
            268435456 + 3, 536870912 + 11, 1073741824 + 85, 0 };

    public StTable(HashFunction<T> hashFunction) {
        this.hashFunction = hashFunction;
        this.num_bins = DEFAULT_SIZE;
        this.num_entries = 0;
        this.bins = (StTableEntry<T, V>[]) new StTableEntry[this.num_bins];
    }

    public StTable(HashFunction<T> hashFunction, int size) {
        this.hashFunction = hashFunction;
        if (size == 0)
            throw new IllegalArgumentException(
                    "The size could not less than zero:" + size);
        this.num_bins = size;
        this.num_entries = 0;
        this.bins = (StTableEntry<T, V>[]) new StTableEntry[this.num_bins];
    }

    private long newSize(int size) {

        for (int i = 0, newsize = DEFAULT_MIN_SIZE; i < primes.length; i++, newsize <<= 1) {
            if (newsize > size)
                return primes[i];
        }
        /* Ran out of polynomials */
        return -1; /* should raise exception */
    }

    public V get(T key) {
        int hash_val = doHash(key);
        StTableEntry<T, V> entry = findEntry(hash_val, key);
        if (entry == null)
            return null;
        else
            return entry.getValue();
    }

    public V put(T key, V value) {
        int hash_val = doHash(key);
        StTableEntry<T, V> entry = findEntry(hash_val, key);
        if (entry == null) {
            // 未有键值，直接添加
            addDirect(key, value);
            return value;
        } else {
            V v = entry.value;
            entry.value = value;
            return v;
        }
    }

    // hash函数，调用hashFunction的hash方法
    private int doHash(T key) {
        if (hashFunction.hash(key) < 0)
            throw new IllegalArgumentException(
                    "hash value could not less than zero:"
                            + hashFunction.hash(key));
        return hashFunction.hash(key);
    }

    // 过于拥挤，重新分布
    public void reHash() {
        int new_size = (int) newSize(this.num_bins);
        StTableEntry<T, V>[] new_bins = (StTableEntry<T, V>[]) new StTableEntry[new_size];
        for (int i = 0; i < this.num_bins; i++) {
            StTableEntry<T, V> entry = this.bins[i];
            while (entry != null) {
                StTableEntry<T, V> next = entry.next;
                int hash_val = entry.hash % new_size;
                entry.next = new_bins[hash_val];
                new_bins[hash_val] = entry;
                entry = next;
            }
        }
        this.bins = null; //gc
        this.num_bins = new_size;
        this.bins = new_bins;

    }

    private void addDirect(T key, V value) {
        int hash_val = doHash(key);
        int bin_pos = hash_val % this.num_bins;
        if ((this.num_entries / this.num_bins) > DEFAULT_MAX_DENSITY) {
            reHash();
            bin_pos = hash_val % this.num_bins;
        }
        StTableEntry<T, V> entry = new StTableEntry<T, V>();
        entry.setHash(hash_val);
        entry.setKey(key);
        entry.setValue(value);
        entry.setNext(this.bins[bin_pos]);
        this.bins[bin_pos] = entry;
        this.num_entries++;
    }

    private StTableEntry<T, V> findEntry(int hash_val, T key) {
        int bin_pos = hash_val % this.num_bins;
        StTableEntry<T, V> entry = this.bins[bin_pos];
        if (entryNotEqual(entry, key, hash_val)) {
            entry = entry.next;
            while (entryNotEqual(entry, key, hash_val)) {
                entry = entry.next;
            }
        }
        return entry;
    }

    // 判断元素是否相同
    private boolean entryNotEqual(StTableEntry<T, V> entry, T key, int hash_val) {
        return entry != null
                && (entry.getHash() != hash_val || (!key.equals(entry.getKey())));
    }

}

   单元测试类就不列了，给一个与HashMap的简单性能对比，以整型为键，显然StTable快多了，对于字符串型，关键是HashFunction的定义，我直接调用String的hashCode方法，不知道有没有其他更好的方法让元素分布的更均匀些：

java 代码

import java.util.HashMap;
import java.util.Map;

public class Benchmark {
    public static void main(String args[]) {
        long map_cost = testStringMap();
        long table_cost = testStringTable();
        if (map_cost <= table_cost)
            System.out.println("map is faster than table ");
        else
            System.out.println("table is faster than map ");

        map_cost = testIntegerMap();
        table_cost = testIntegerTable();
        if (map_cost <= table_cost)
            System.out.println("map is faster than table ");
        else
            System.out.println("table is faster than map ");
    }

    public static long testIntegerMap() {
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        long start = System.nanoTime();
        for (int i = 0; i < 10000; i++)
            map.put(i, i);
        long result = 0;
        for (int i = 0; i < 10000; i++)
            result += map.get(i);
        long end = System.nanoTime();
        System.out.println("result:" + result);
        System.out.println("map:" + (end - start));
        return (end - start);
    }

    public static long testIntegerTable() {
        HashFunction<Integer> intHash = new HashFunction<Integer>() {
            public int hash(Integer key) {
                return key;
            }
        };
        StTable<Integer, Integer> table = new StTable<Integer, Integer>(intHash);
        long start = System.nanoTime();
        for (int i = 0; i < 10000; i++)
            table.put(i, i);
        long result = 0;
        for (int i = 0; i < 10000; i++)
            result += table.get(i);
        long end = System.nanoTime();
        System.out.println("result:" + result);
        System.out.println("table:" + (end - start));
        return (end - start);
    }

    public static long testStringMap() {
        Map<String, String> map = new HashMap<String, String>();
        long start = System.nanoTime();
        for (int i = 0; i < 10000; i++)
            map.put(String.valueOf(i), String.valueOf(i));
        long result = 0;
        for (int i = 0; i < 10000; i++)
            result += Integer.parseInt(map.get(String.valueOf(i)));
        long end = System.nanoTime();
        System.out.println("result:" + result);
        System.out.println("map:" + (end - start));
        return (end - start);
    }

    public static long testStringTable() {
        HashFunction<String> intHash = new HashFunction<String>() {
            int i = 0;
            public int hash(String key) {
                int hashCode = key.hashCode();
                return hashCode < 0 ? -hashCode : hashCode;
            }
        };
        StTable<String, String> table = new StTable<String, String>(intHash);
        long start = System.nanoTime();
        for (int i = 0; i < 10000; i++)
            table.put(String.valueOf(i), String.valueOf(i));
        long result = 0;
        for (int i = 0; i < 10000; i++)
            result += Integer.parseInt(table.get(String.valueOf(i)));
        long end = System.nanoTime();
        System.out.println("result:" + result);
        System.out.println("table:" + (end - start));
        return (end - start);
    }

}

结果为：
result:49995000
map:55501468
result:49995000
table:60999652
map is faster than table

 
result:49995000
map:44634444
result:49995000
table:26209477
table is faster than map