public class MyHashtable {

    //表中元素个数

    private int manyItems;

    private Object[] keys;

    private Object[] data;

    //若索引i处存在元素，则hasBeenUsed[i]为true，否则为false

    private boolean[] hasBeenUsed;

    //构造函数

    public MyHashtable(int capacity){

        if(capacity <= 0){

            throw new IllegalArgumentException("capacity is negative!");

        }

        keys = new Object[capacity];

        data = new Object[capacity];

        hasBeenUsed = new boolean[capacity];

    }

    //hash函数

    private int hash(Object key){

        return Math.abs(key.hashCode()%data.length);

    }

    //当前索引发生冲突，找下一索引

    private int nextIndex(int i){

        if(i + 1 == data.length){

            return 0;

        }else{

            return i + 1;

        }

    }

    /*

     * 如果在表中找到指定的关键字，返回值为关键字的索引，否则返回-1

     * 也就是说如果已经存在某个键时，返回的是该键的索引，如果没有这个键，则返回-1

     * 在插入新的键时都返回-1

     */

    private int findIndex(Object key){

        int count = 0;

        int i = hash(key);

        System.out.println(i);

        while((count<data.length)&&hasBeenUsed[i]){

            if(key.equals(keys[i])){

                return i;

            }else{

                count++;

                i = nextIndex(i);

            }

        }

        return -1;

    }

    /*

     * 获取某个元素

     */

    public Object get(Object key){

        int index = findIndex(key);

        if(index == -1){

            return null;

        }

        else{

            return data[index];

        }

    }

    /*

     * 放入某个元素

     */

    public Object put(Object key,Object element){

        int index = findIndex(key);

        Object answer;

        //判断索引是不是-1

        if(index != -1){

            answer = data[index];

            data[index] = element;

            return answer;

        }else if(manyItems<data.length){

            index = hash(key);

            while(keys[index] != null){

                index = nextIndex(index);

            }

            keys[index] = key;

            data[index] = element;

            hasBeenUsed[index] = true;

            manyItems++;

            return null;

        }else{

            throw new IllegalStateException("Hsahtable is full");

        }

    }

    /*

     * 删除某个元素

     */

    public Object remove(Object key){

        int index = findIndex(key);

        Object answer = null;

        if(index != -1){

            answer = data[index];

            data[index] = null;

            keys[index] = null;

            manyItems--;

        }

        return answer;

    }

    /*

     * 是否包含某键

     */

    public boolean contains(Object key){

        return (findIndex(key)!=-1);

    }

    public static void main(String[] args) {

        // TODO Auto-generated method stub

        MyHashtable table = new MyHashtable(3);

        table.put(1, "中国");

        Object ob1 = table.put(2, "美国");

        table.put(3, "安徽");

        System.out.println(table.get(2).toString());

        System.out.println(ob1);

    }

}