JAVA数据结构之哈希表
hash表的优缺点
hash表比树形结构快的原因,表的是位置是计算出来的通过hash函数,满足随机插入的结构。但是在有该优点的情况下,需要考虑哈希冲突
本例结构中采用链地址法【在hash表的每一个表单元,都是链表结构,发生冲突的元素,自动加入链表】 在jdk8以前采用的是链表解决,在jdk8之后,在处理哈希冲突时,先采用链表,当链表中size大于8时,转化为树形结构,采用的红黑树结构。
//不需要像二分搜索树一样 键值实现可比较,只需要能实现hashCode 但每一个对象都是继承自Object 所以都有hashCode方法 public class HashTable<K, V> { private final int[] capacity = { 53, 97, 193, 389, 769, 1543, 3079, 6151, 12289, 24593, 49157, 98317, 196613, 393241, 786433, 1572869, 3145739, 6291469, 12582917, 25165843, 50331653, 100663319, 201326611, 402653189, 805306457, 1610612741}; private static final int upperTol = 10; private static final int lowerTol = 2; private int CapacityIndex = 0; private TreeMap<K, V>[] hashtable; private int M;//设置哈希表数组长度,选择一个合适的素数 private int size;//已经存储的元素个数 public HashTable() { this.M = capacity[CapacityIndex]; this.size = 0; hashtable = new TreeMap[M];//只是开出了空间,还需要对每个空间进行实例化 for (int i = 0; i < M; i++) { hashtable[i] = new TreeMap<>(); } } private int hash(K key) { return (key.hashCode() & 0x7fffffff) % M;//消除掉key对应的hashCode的符号 } public int getSize() { return size; } public void add(K key, V value) { TreeMap<K, V> map = hashtable[hash(key)]; if (map.containsKey(key)) { map.put(key, value); } else { map.put(key, value); size++; } //判断数组越界问题 if (size >= upperTol * M && CapacityIndex + 1 < capacity.length) { CapacityIndex++; resize(capacity[CapacityIndex]); } } public V remove(K key) { TreeMap<K, V> map = hashtable[hash(key)]; V ret = null; if (map.containsKey(key)) { ret = map.remove(key); size--; } if (size < lowerTol * M && CapacityIndex - 1 >= 0) { CapacityIndex--; resize(capacity[CapacityIndex]); } return ret; } public void set(K key, V value) { TreeMap<K, V> map = hashtable[hash(key)]; if (!map.containsKey(key)) { throw new IllegalArgumentException(key + "doesnt exist"); } else { map.put(key, value); } } public boolean contains(K key) { return hashtable[hash(key)].containsKey(key); } public V get(K key) { return hashtable[hash(key)].get(key); } private void resize(int newM) { TreeMap<K, V>[] newHashTable = new TreeMap[newM]; for (int i = 0; i < newM; i++) { newHashTable[i] = new TreeMap<>(); } int oldM = M; this.M = newM;//在hash()中会用到新的的M //必须重新给M赋值!!! for (int i = 0; i < oldM; i++) { TreeMap<K, V> map = hashtable[i]; for (K key : map.keySet()) { newHashTable[hash(key)].put(key, map.get(key)); } } this.hashtable = newHashTable; } }