摘要:简介声明文章均为本人技术笔记,转载请注明出处声明和一样也是散列表,存储元素也是键值对继承于类类声明了操作键值对的接口方法,实现接口定义键值对接口大部分类用修饰,证明是线程安全的基本数据结构键值对数组,每个本质上是一个单向链表的表头阈值装填因
Hashtable简介 声明
文章均为本人技术笔记,转载请注明出处https://segmentfault.com/u/yzwall
Hashtable声明public class Hashtable
extends Dictionary implements Map , Cloneable, java.io.Serializable
Hashtable和HashMap一样也是散列表,存储元素也是键值对;
Hashtable继承于Dictionary类(Dictionary类声明了操作键值对的接口方法),实现Map接口(定义键值对接口);
Hashtable大部分类用synchronized修饰,证明Hashtable是线程安全的;
private transient Entry,?>[] table:键值对/Entry数组,每个Entry本质上是一个单向链表的表头
private int threshold:rehash阈值
private float loadFactor:装填因子
private transient int modCount = 0: Hashtable结构化修改次数,用来实现fail-fast机制;
private transient volatile Set
private transient volatile Set
private transient volatile Collection
Hashtable中key和value是一对多关系;
键值对/Entryprivate static class EntryHash函数implements Map.Entry { final int hash; final K key; V value; Entry next; ... // 计算键值对的hashCode public int hashCode() { // "^" 按位异或, hash在调用构造器时传入 return hash ^ Objects.hashCode(value); } }
键值对
Hashtable方法分析 public synchronized boolean contains(Object value)public boolean containsValue(Object value)内部调用contains(value);
判断是否含有该value的键值对,在Hashtable中hashCode相同的Entry用链表组织,hashCode不同的存储在Entry数组table中;
// in contains() method. Entry,?> tab[] = table; // 查找:遍历所有Entry链表 for (int i = tab.length ; i-- > 0 ;) { for (Entry,?> e = tab[i] ; e != null ; e = e.next) { if (e.value.equals(value)) { return true; } } } return false;public synchronized boolean containsKey(Object key)
int index = (hash & 0x7FFFFFFF) % tab.length;
计算键值对的桶位(本质是键值对在tab数组中的索引),Hashtable本质上采用除数取余法进行散列分布,模运算效率较低
int hash = key.hashCode() Hashtable直接调用key的hashCode()计算hashCode;
Entry,?> tab[] = table; int hash = key.hashCode(); /** * 计算index, % tab.length防止数组越界 * index表示key对应entry所在链表表头 */ int index = (hash & 0x7FFFFFFF) % tab.length; for (Entry,?> e = tab[index] ; e != null ; e = e.next) { if ((e.hash == hash) && e.key.equals(key)) { return true; } } return false;
public synchronized V get(Object key):根据指定key查找对应value,查找原理与containsKey相同,查找成功返回value,否则返回null;
public synchronized V put(K key, V value)设置键值对,key和value都不可为null,设置顺序:
如果Hashtable含有key,设置(key, oldValue) -> (key, newValue);
如果Hashtable不含有key, 调用addEntry(...)添加新的键值对;
当键值对个数超过阈值,先进行rehash然后添加entry,否则直接添加entry;
public synchronized V remove(Object key)remove操作,计算key所在链表表头table[index],然后进行单向链表的节点删除操作
public synchronized Object clone()对Hashtable的浅拷贝操作,浅拷贝所有bucket(单向链表组织形式)的表头;
protected void rehash()当Hashtable中键值对总数超过阈值(容量*装载因子)后,内部自动调用rehash()增加容量,重新计算每个键值对的hashCode;
int newCapacity = (oldCapacity << 1) + 1计算新容量 = 2 * 旧容量 + 1;并且根据新容量更新阈值;
... for (int i = oldCapacity ; i-- > 0 ;) { // 拷贝每个Entry链表 for (Entryold = (Entry )oldMap[i] ; old != null ; ) { Entry e = old; old = old.next; // 重新计算每个Entry链表的表头索引(rehash) int index = (e.hash & 0x7FFFFFFF) % newCapacity; // 开辟链表节点 e.next = (Entry )newMap[index]; // 拷贝 newMap[index] = e; } }
文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。
转载请注明本文地址:https://www.ucloud.cn/yun/66972.html
摘要:所谓拉链法就是将链表和数组相结合。若遇到哈希冲突,则将冲突的值加到链表中即可。在编写程序中,要尽量避免。 目录: 0-1. 简介 0-2. 内部结构分析 0-2-1. JDK18之前 0-2-2. JDK18之后 0-3. LinkedList源码分析 0-3-1. 构造方法 0-3-2. put方法 0-3-3. get方法 0-3-4. resize方法 ...
摘要:若遇到哈希冲突,则将冲突的值加到链表中即可。之后相比于之前的版本,之后在解决哈希冲突时有了较大的变化,当链表长度大于阈值默认为时,将链表转化为红黑树,以减少搜索时间。有序,唯一红黑树自平衡的排序二叉树。 本文是最最最常见Java面试题总结系列第三周的文章。主要内容: Arraylist 与 LinkedList 异同 ArrayList 与 Vector 区别 HashMap的底层...
摘要:当一个值中要存储到的时候会根据的值来计算出他的,通过哈希来确认到数组的位置,如果发生哈希碰撞就以链表的形式存储在源码分析中解释过,但是这样如果链表过长来的话,会把这个链表转换成红黑树来存储。 正文开始 注:JDK版本为1.8 HashMap1.8和1.8之前的源码差别很大 目录 简介 数据结构 类结构 属性 构造方法 增加 删除 修改 总结 1.HashMap简介 H...
摘要:三系列用于保存键值对,无论是,还是已弃用的或者线程安全的等,都是基于红黑树。是完全基于红黑树的,并在此基础上实现了接口。可以看到,只有红黑树,且红黑树是通过内部类来实现的。 JDK容器 前言 阅读JDK源码有段时间了,准备以博客的形式记录下来,也方便复习时查阅,本文参考JDK1.8源码。 一、Collection Collection是所有容器的基类,定义了一些基础方法。List、Se...
阅读 1961·2021-11-22 15:33
阅读 3002·2021-11-18 10:02
阅读 2605·2021-11-08 13:16
阅读 1619·2021-10-09 09:57
阅读 1366·2021-09-30 09:47
阅读 2002·2019-08-29 13:05
阅读 3065·2019-08-29 12:46
阅读 1004·2019-08-29 12:19