java中的哈希表

哈希表优点：增删查 时间复杂度O(1)；            缺点：1.占用内存较大 2.元素没有任何顺序；

class LinerHashMap<T extends Comparable<T>>{ // 散列表数组 private Entry<T>[] hashTable; // 被占用的桶的个数 private int usedBucketNum; // 哈希表的装载因子 private double loadFactor; // 定义素数表 private static int[] primTable; // 记录当前使用的素数的下标 private int primIndex; // 类的静态初始化块 static{ primTable = new int[]{3, 7, 23, 47, 97, 127}; } /** * 构造函数，初始化 */ public LinerHashMap(){ this.primIndex = 0; this.hashTable = new Entry[primTable[this.primIndex]]; this.usedBucketNum = 0; this.loadFactor = 0.75; } /** * 增加元素 * @param key */ public void put(T key){ // 计算哈希表是否需要扩容 double ret = this.usedBucketNum*1.0 / this.hashTable.length; if(ret > this.loadFactor){ resize(); // 哈希表的扩容 } // 先计算key应该放的桶的下标 int index = key.hashCode() % this.hashTable.length;//hashCode是使这个元素取整数 int idx = index; do{ // 表示是从未使用过的桶 if(this.hashTable[index] == null){ this.hashTable[index] = new Entry<>(key, State.USING); this.usedBucketNum++; return; } // 表示使用过的桶 if(this.hashTable[index].getState() == State.USED){ this.hashTable[index].setData(key); this.hashTable[index].setState(State.USING); this.usedBucketNum++; return; } else { // 正在使用中的桶，不插入重复元素 if(this.hashTable[index].getData().compareTo(key) == 0){ return; } } idx = (idx+1)%this.hashTable.length; } while(idx != index); } /** * 哈希表的扩容函数 */ private void resize() { Entry<T>[] oldHashTable = this.hashTable; this.hashTable = new Entry[primTable[++this.primIndex]]; this.usedBucketNum = 0; for (int i = 0; i < oldHashTable.length; i++) { if(oldHashTable[i] != null && oldHashTable[i].getState() == State.USING){ this.put(oldHashTable[i].getData()); } } } /** * 删除元素 * @param key */ public void remove(T key){ // 先计算key应该放的桶的下标 int index = key.hashCode() % this.hashTable.length; // 从当前位置开始找元素 int idx = index; do{ // 如果遍历桶的过程中，发现了从未使用过的桶，直接返回 if(this.hashTable[idx] == null){ return; } if(this.hashTable[idx].getState() == State.USING && this.hashTable[idx].getData().compareTo(key) == 0){ this.hashTable[idx].setData(null); this.hashTable[idx].setState(State.USED); this.usedBucketNum--; return; } idx = (idx+1)%this.hashTable.length; } while(idx != index); } /** * 查询元素 返回key的值，找不到返回null * HashMap * @param key * @return */ public T get(T key){ // 先计算key应该放的桶的下标 int index = key.hashCode() % this.hashTable.length; // 从当前位置开始找元素 int idx = index; do{ // 如果遍历桶的过程中，发现了从未使用过的桶，直接返回 if(this.hashTable[idx] == null){ return null; } if(this.hashTable[idx].getState() == State.USING && this.hashTable[idx].getData().compareTo(key) == 0){ return key; } idx = (idx+1)%this.hashTable.length; } while(idx != index); return null; } /** * 定义桶的状态值 */ static enum State{ UNUSE,// 桶从未使用过 USED,// 桶被用过了 USING// 桶正在使用中 } /** * 定义桶的元素类型 * @param <T> */ static class Entry<T extends Comparable<T>>{ T data; State state; public Entry(T data, State state) { this.data = data; this.state = state; } public T getData() { return data; } public void setData(T data) { this.data = data; } public State getState() { return state; } public void setState(State state) { this.state = state; } } }