大家好,又见面了,我是你们的朋友全栈君。
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 + "doesn't 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;
}
}
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/126574.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...