散列表

它是用一个散列函数把关键字 映射到散列表中的特定位置。 在理想情况下，如果元素e 的关键字为k，散列函 数为f，那么e 在散列表中的位置为f (k)。要搜索关键字为k 的元素，首先要计算出f (k)，然后看 表中f (k)处是否有元素。如果有，便找到了该元素。如果没有，说明该字典中不包含该元素。 在前一种情况中，如果要删除该元素，只需把表中f (k)位置置为空即可。在后一种情况中，可 以通过把元素放在f (k)位置以实现插入。 此例是一个理想情况下的散列表，不考虑关键字重复的情况

public class HashList {            PRivate String[] table;    private int size;    private int threshold;    private static final int INITIAL_CAPACITY = 10;    private static final int SIZE_INCREASE = 10;    private static final float DEFAULT_LOAD_FACTOR = 0.75f;                public HashList(){        threshold = (int)(INITIAL_CAPACITY*DEFAULT_LOAD_FACTOR);        table = new String[INITIAL_CAPACITY];    }                public HashList(String[] table){        this.table = table;    }                    /**     * Get the actual size of the list     * @return     */    public int size(){        return size;    }        /**     * for test     * @return     */    public String[] getElements(){        return table;    }        public boolean contains(String element) {        if (element == null) {            return false;        }        if (element.equals(table[getIndex(element)])) {            return true;        }        return false;    }        public void add(String element){        int index = getIndex(element);        if(size>threshold){            resize();        }        table[index] = element;        size++;    }                //private methods    /**     * resize the array     */    private void resize(){        String[] newArray = new String[table.length+SIZE_INCREASE];        for(int i=0;i<table.length;i++){            newArray[i] = table[i];        }        table = newArray;        threshold = (int)(table.length*DEFAULT_LOAD_FACTOR);    }        /**     * get the index of the element     * @param element     * @return     */    public int getIndex(String element) {        return (element.hashCode() & 0x7FFFFFFF) % table.length;    }    }