java（八）集合（3）

集合三、HashTable 1、HashTable继承Dictionary类，实现Map接口。其中Dictionary类是任何可将键映射到相应值的类的抽象父类。Hashtable中有几个比较重要的参数：1）table：为一个Entry[]数组类型，Entry代表了“拉链”的节点，每一个Entry代表了一个键值对，哈希表的"key-value键值对"都是存储在Entry数组中的。2）loadFactor：加载因子。3）count：HashTable的大小，是指他所包含Entry键值对的数量。不是指容器大小。4）threshold：Hashtable的阈值，用于判断是否需要调整Hashtable的容量。threshold的值="容量*加载因子"。5）modCount：用来实现“fail-fast”机制的，所谓快速失败就是在并发集合中，其进行迭代操作时，若有其他线程对其进行结构性的修改，这时迭代器会立马感知到，并且立即抛出ConcurrentModificationException异常，而不是等到迭代完成之后才告诉你出错。 2、构造函数：1）public Hashtable() {        this(11, 0.75f);    }构造初始容量11，与加载因子0.75的哈希表。2）指定初始容量和默认加载因子 this(initialCapacity, 0.75f);3）public Hashtable(int initialCapacity, float loadFactor)指定两个参数。4)public Hashtable(Map<? extends K, ? extends V> t) {        //设置table容器大小，其值==t.size * 2 + 1        this(Math.max(2*t.size(), 11), 0.75f);        putAll(t);    }  构造一个与给定的 Map 具有相同映射关系的新哈希表。 3、Hashtable的存与取方法： public synchronized V put(K key, V value) {//向哈希表中添加键值对 // Make sure the value is not null if (value == null) {//确保值不能为空 throw new NullPointerException(); } // Makes sure the key is not already in the hashtable. Entry tab[] = table; int hash = hash(key);//根据键生成hash值---->若key为null，此方法会抛异常 int index = (hash & 0x7FFFFFFF) % tab.length;//通过hash值找到其存储位置 for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {/遍历链表 if ((e.hash == hash) && e.key.equals(key)) {//若键相同，则新值覆盖旧值 V old = e.value; e.value = value; return old; } } modCount++; if (count >= threshold) {//当前容量超过阈值。需要扩容 // Rehash the table if the threshold is exceeded rehash();//重新构建桶数组，并对数组中所有键值对重哈希，耗时！ tab = table; hash = hash(key); index = (hash & 0x7FFFFFFF) % tab.length;//这里是取摸运算 } // Creates the new entry. Entry<K,V> e = tab[index]; //将新结点插到链表首部 tab[index] = new Entry<>(hash, key, value, e);//生成一个新结点 count++; return null; } Hasbtable：1）并不允许值和键为空（null），若为空，会抛空指针put方法在开始处仅对value进行判断，并未对key判断，因为当调用hash方法时，若key为空，依然会抛出空指针异常。2）HashMap计算索引的方式是h&(length-1),而Hashtable用的是模运算，效率上是低于HashMap的。3）另外Hashtable计算索引时将hash值先与上0x7FFFFFFF,这是为了保证hash值始终为正数。4）特别需要注意的是这个方法包括下面要讲的若干方法都加了synchronized关键字，也就意味着这个Hashtable是个线程安全的类，这也是它和HashMap最大的不同点. 添加元素流程为：计算key的hash值根据hash值获得key在table数组中的索引位置，然后迭代该key处的Entry链表，若该链表中存在一个这个的key对象，那么就直接替换其value值即可，否则在将改key-value节点插入该index索引位置处。再添加元素是会进行扩容操作，扩容代码为： protected void rehash() { int oldCapacity = table.length;//记录旧容量 Entry<K,V>[] oldMap = table;//记录旧的桶数组 // overflow-conscious code int newCapacity = (oldCapacity << 1) + 1;//新容量为老容量的2倍加1 if (newCapacity - MAX_ARRAY_SIZE > 0) { if (oldCapacity == MAX_ARRAY_SIZE)//容量不得超过约定的最大值 // Keep running with MAX_ARRAY_SIZE buckets return; newCapacity = MAX_ARRAY_SIZE; } Entry<K,V>[] newMap = new Entry[newCapacity];//创建新的数组 modCount++; threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1); boolean currentAltHashing = useAltHashing; useAltHashing = sun.misc.VM.isBooted() && (newCapacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD); boolean rehash = currentAltHashing ^ useAltHashing; table = newMap; for (int i = oldCapacity ; i-- > 0 ;) {//转移键值对到新数组 for (Entry<K,V> old = oldMap[i] ; old != null ; ) { Entry<K,V> e = old; old = old.next; if (rehash) { e.hash = hash(e.key); } int index = (e.hash & 0x7FFFFFFF) % newCapacity; e.next = newMap[index]; newMap[index] = e; } } } Hashtable每次扩容，容量都为原来的2倍加2，而HashMap为原来的2倍。 获取代码为： public synchronized V get(Object key) {//根据键取出对应索引 Entry tab[] = table; int hash = hash(key);//先根据key计算hash值 int index = (hash & 0x7FFFFFFF) % tab.length;//再根据hash值找到索引 for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {//遍历entry链 if ((e.hash == hash) && e.key.equals(key)) {//若找到该键 return e.value;//返回对应的值 } } return null;//否则返回null } 如果你传的参数为null，是会抛空指针。 1）Hashtable是个线程安全的类（HashMap线程不安全）； 2）Hasbtable并不允许值和键为空（null），若为空，会抛空指针（HashMap可以）； 3）Hashtable不允许键重复，若键重复，则新插入的值会覆盖旧值（同HashMap）； 4）Hashtable同样是通过链表法解决冲突； 5）Hashtable根据hashcode计算索引时将hashcode值先与上0x7FFFFFFF,这是为了保证hash值始终为正数; 6）Hashtable的容量为任意正数（最小为1），而HashMap的容量始终为2的n次方。Hashtable默认容量为11，HashMap默认容量为16； 7）Hashtable每次扩容，新容量为旧容量的2倍加2，而HashMap为旧容量的2倍； 8）Hashtable和HashMap默认负载因子都为0.75; 哈希码。集合是分两类List与set，list有序可重复，set无须不重复，再添加元素是每次equals方法判断，在大量元素是会造成效率低下，哈希码是散列算法是将数据依特定算法直接指定到一个地址上，当集合要添加新的元素时，先调用这个元素的hashCode方法，就一下子能定位到它应该放置的物理位置上。Java对于eqauls方法和hashCode方法是这样规定的： 1、如果两个对象相同，那么它们的hashCode值一定要相同； 2、如果两个对象的hashCode相同，它们并不一定相同。 hashcode与equals的使用 equals()是对两个对象的地址值进行的比较（即比较引用是否相同）。 hashCode()是一个本地方法，它的实现是根据本地机器相关的。 Java语言对equals()的要求如下，这些要求是必须遵循的： A 对称性：如果x.equals(y)返回是“true”，那么y.equals(x)也应该返回是“true”。 B 反射性：x.equals(x)必须返回是“true”。 C 类推性：如果x.equals(y)返回是“true”，而且y.equals(z)返回是“true”，那么z.equals(x)也应该返回是“true”。 D 一致性：如果x.equals(y)返回是“true”，只要x和y内容一直不变，不管你重复x.equals(y)多少次，返回都是“true”。 任何情况下，x.equals(null)，永远返回是“false”；x.equals(和x不同类型的对象)永远返回是“false”。 equals()相等的两个对象，hashcode()一定相等；反过来：hashcode()不等，一定能推出equals()也不等；hashcode()相等，equals()可能相等，也可能不等。