网站建设与优化计入什么科莫,外发加工流程管理制度,怎么在国际网站做推广,网站开发怎么挣外快很多人都知道HashTable与HashMap的关系#xff0c;HashTable是线程安全的#xff0c;HashMap是非线程安全的。在介绍完HashMap之后#xff0c;趁热介绍一下HashTable。在HashTable中没有像HashMap中那么多关于数据结构的内容。HashTable是线程安全的#xff0c;因为其源码的…很多人都知道HashTable与HashMap的关系HashTable是线程安全的HashMap是非线程安全的。在介绍完HashMap之后趁热介绍一下HashTable。在HashTable中没有像HashMap中那么多关于数据结构的内容。HashTable是线程安全的因为其源码的方法里都带有synchronized但是效率不高如果想使用高性能的Hash结构建议使用java.util.concurrent.ConcurrentHashMap HashTable 存储的数据类型 HashTable的key和value都可以为空在存储的过程中 key必须实现 hashCode和equals两个方法。 影响HashTable性能的两个参数 HashTable中的两个变量影响其性能初始容量与负载系数load factor。 容量 指的时hashtable中桶的个数。桶其实就是单向的链表。hashtable 是允许hash 冲突的单个桶链表可以存储多个entry。在定义HashTable的初始容量的大小时要权衡是空间 和 重新hash运算很耗时之间的利弊。当初始的容量大于元素的最大个数时将不会发生rehash运算但是太大的初始容量意味着浪费了很多空间。如果能提前估算出要向hashTable中存很多值时就要给一个适合的初始容量因为在添加数据时如果不需要rehash操作的话将会更快。 负载系数 指的是hashtable在自动扩容之前允许桶多满默认的负载系数为0.75增大可以减少每次扩容的大小但是增加了查找所花费的时间。 数据结构 前面也提到了HashTable内部存储了一个table数组这个数组的每一个元素存储的都是链表的头。在存储数值时定位存储位置是通过如下代码 int hash key.hashCode();int index (hash 0x7FFFFFFF) % tab.length; // 去掉符号位的影响EntryK,V e (EntryK,V)tab[index]; 上面的代码就确定了当前key的节点位于哪个链表上e 即链表头。如果在该链表中无法找到对应的key则将当前的节点添加到链表的头部。 EntryK,V e (EntryK,V) tab[index];// 把链表的头部传进去为了将new 出来的节点.next指向原来链表的头部tab[index] new Entry(hash, key, value, e); rehash算法 rehash算法也可以理解为扩容算法当table装不下要存储的值的时候这是后就需要扩容增加内部数组的长度这下惨了每个key存储到哪个链表中是和table.length有直接关系的所以在扩容时要把当前hashtable中存储的节点重新计算一遍存储位置这就是前面提到的为什么rehash会很耗时。 protected void rehash() {int oldCapacity table.length;Entry?,?[] oldMap table;// overflow-conscious codeint newCapacity (oldCapacity 1) 1; // 容量每次扩大一倍if (newCapacity - MAX_ARRAY_SIZE 0) {if (oldCapacity MAX_ARRAY_SIZE)// Keep running with MAX_ARRAY_SIZE bucketsreturn;newCapacity MAX_ARRAY_SIZE;}Entry?,?[] newMap new Entry?,?[newCapacity];modCount; //结构变化threshold (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE 1);table newMap;for (int i oldCapacity ; i-- 0 ;) {for (EntryK,V old (EntryK,V)oldMap[i] ; old ! null ; ) {EntryK,V e old; // 将当前的变量赋值给暂存变量old old.next; // 继续获取链表的下一个节点为下一次循环做准备int index (e.hash 0x7FFFFFFF) % newCapacity; // 计算当前节点在newMap中存储的位置// 每次插入数据都插入到链表的头e.next (EntryK,V)newMap[index]; // 将当前节点的指针指向原来链表的头newMap[index] e; // 将当且节点存入数组中}}
} compute方法 这不是hashMap独有的是Map接口定义的。放在这里讲的原因是HashTable没什么好写的正好从HashMap把这部分内容搬过来。 computeIfAbsentcomputeIfPresentcompute 三个方法这三个方法本质上都是根据给定的key更新当前map中的值HashMap中也有同样的方法 下面是一个简短的例子 public static void main(String[] args) {
HashMapString,Integer map new HashMap();
for (int i 0; i 10; i) {
map.put(String.valueOf(i),i);
}
map.computeIfPresent(String.valueOf(5),new MyFunction()); // 如果存在则计算
System.out.println(map);map.computeIfAbsent(String.valueOf(20),new AbsentFunciton()); //如果不存在添加
System.out.println(map);map.compute(String.valueOf(8),new MyFunction()); //如果存在则计算不存在添加
System.out.println(map);
}//上面要使用的接口实现
class MyFunction implements BiFunction {Overridepublic Object apply(Object key, Object oldValue) {if (key.equals(5)) {return (Integer)oldValue 3;}return oldValue;}
}class AbsentFunciton implements Function{Overridepublic Object apply(Object key) {return key;}
} 下面对3个方法进行一下介绍 computeIfAbsent 根据给定的key 在hashtable中查找如果找到了返回key对应的值如果没找到根据定义的计算功能算出新值如果新值不为空添加到hashtable中 public synchronized V computeIfAbsent(K key, Function? super K, ? extends V mappingFunction) {//计算功能不能为空Objects.requireNonNull(mappingFunction);// 缓存内部tableEntry?,? tab[] table;// 根据给定的key 计算出hashint hash key.hashCode();// 根据hash求出在数组第几个链上int index (hash 0x7FFFFFFF) % tab.length;SuppressWarnings(unchecked)EntryK,V e (EntryK,V)tab[index];// 如果在链表中找到则返回旧值for (; e ! null; e e.next) {if (e.hash hash e.key.equals(key)) {// Hashtable not accept null valuereturn e.value;}}// 记录modCount 在计算时不允许修改hashtable结构int mc modCount;// 获得根据计算功能计算出的新值V newValue mappingFunction.apply(key);if (mc ! modCount) { throw new ConcurrentModificationException(); }// 如果新值不为空添加到hashtable中if (newValue ! null) {addEntry(hash, key, newValue, index);}// 返回新值return newValue;
} computeIfPresent 根据给定的key在hashtable中查找如果没找到返回空如果找到了根据定义的功能计算出新值如果新值为 null则将key对应的节点删除如果不是空更新节点值,最后返回新值。 public synchronized V computeIfPresent(K key, BiFunction? super K, ? super V, ? extends V remappingFunction) {//定义的计算功能不能为空Objects.requireNonNull(remappingFunction);//复制一份tableEntry?,? tab[] table;// 根据hash计算在hashtable中的位置int hash key.hashCode();int index (hash 0x7FFFFFFF) % tab.length;SuppressWarnings(unchecked)EntryK,V e (EntryK,V)tab[index];// 在对应的位置的链表中查找for (EntryK,V prev null; e ! null; prev e, e e.next) {if (e.hash hash e.key.equals(key)) {// 如果找到了根据key、旧值和定义的功能计算出新值 int mc modCount;V newValue remappingFunction.apply(key, e.value);if (mc ! modCount) {throw new ConcurrentModificationException();}// 要将新值赋值到原来的key上如果新值为空则要在链表上删除对应的节点计数器-1if (newValue null) {if (prev ! null) {prev.next e.next; } else {tab[index] e.next;}modCount mc 1;count--;} else {e.value newValue;}// 返回新值return newValue;}}// 如果在对应位置上的链表中没有找到则返回空return null;
} compute 思路就是有就更新没有就添加是上面两个的整合。 public synchronized V compute(K key, BiFunction? super K, ? super V, ? extends V remappingFunction) {// 定义的计算功能不能为空Objects.requireNonNull(remappingFunction);Entry?,? tab[] table;// 根据hash获取链表位置int hash key.hashCode();int index (hash 0x7FFFFFFF) % tab.length;SuppressWarnings(unchecked)EntryK,V e (EntryK,V)tab[index];如果根据key找到了对应的节点更新对应的节点值并返回根据功能计算的新值for (EntryK,V prev null; e ! null; prev e, e e.next) {if (e.hash hash Objects.equals(e.key, key)) {int mc modCount;V newValue remappingFunction.apply(key, e.value);if (mc ! modCount) {throw new ConcurrentModificationException();}if (newValue null) {if (prev ! null) {prev.next e.next;} else {tab[index] e.next;}modCount mc 1;count--;} else {e.value newValue;}return newValue;}}// 如果没有找到根据key 计算出新值如果新值不为空添加到table中返回计算的新值int mc modCount;V newValue remappingFunction.apply(key, null);if (mc ! modCount) { throw new ConcurrentModificationException(); }if (newValue ! null) {addEntry(hash, key, newValue, index);}return newValue;
} 转载于:https://www.cnblogs.com/arax/p/8206702.html
