资讯专栏INFORMATION COLUMN

【java源码一带一路系列】之Hashtable

william / 2872人阅读

摘要:从上往下看的源码,标注了路上一些景点。感兴趣的同学可以继续跟,它返回的是一个内部实现的类实现了。此外,循环中的新旧数据迁移的行代码也很经典。一词成功引起了笔者注意。与之对应的是深拷贝。里面的对象会在原来的对象和它的副本之间共享。

从上往下看的源码,标注了路上一些“景点”。皮皮虾,我们走。
/**
 * Constructs a new hashtable with the same mappings as the given
 * Map.  The hashtable is created with an initial capacity sufficient to
 * hold the mappings in the given Map and a default load factor (0.75).
 *
 * @param t the map whose mappings are to be placed in this map.
 * @throws NullPointerException if the specified map is null.
 * @since   1.2
 */
public Hashtable(Map t) {
    this(Math.max(2*t.size(), 11), 0.75f);
    putAll(t);
}

initialCapacity不指定的话是默认11;

这里多带带列出这个初始化方法,主要是因为这个2*t.size(),如果你还记得的话,在第二路文中介绍HashMap.resize()时,它就是按2扩容的。

/**
 * Returns an enumeration of the keys in this hashtable.
 *
 * @return  an enumeration of the keys in this hashtable.
 * @see     Enumeration
 * @see     #elements()
 * @see     #keySet()
 * @see     Map
 */
public synchronized Enumeration keys() {
    return this.getEnumeration(KEYS);
}

// Types of Enumerations/Iterations
private static final int KEYS = 0;
private static final int VALUES = 1;
private static final int ENTRIES = 2;

看到synchronized想说的是HashTable是同步,所以大多数方法都可见进行了同步处理,这点与HashMap不同(其他差别:HashTable的key、value都不允许为null)。该方法通过Enumeration遍历Hashtable的键(KEYS是定义的全局变量),类似的,还有通过Enumeration遍历Hashtable的值。感兴趣的同学可以继续跟getEnumeration(),它返回的是一个hashtable内部实现的Enumerator类(实现了Enumeration, Iterator)。
应用实例如下:

Enumeration enu = table.keys();
while(enu.hasMoreElements()) {
    System.out.println(enu.nextElement());
} 
/**
 * The maximum size of array to allocate.
 * Some VMs reserve some header words in an array.
 * Attempts to allocate larger arrays may result in
 * OutOfMemoryError: Requested array size exceeds VM limit
 */
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

这里好奇的是“-8”从何而来?从stackoverflow得到的答案是(译):

数组(ARRAY)需要用8bytes来存储(2^31 = 2,147,483,648 )大小(size)。

/**
 * Increases the capacity of and internally reorganizes this
 * hashtable, in order to accommodate and access its entries more
 * efficiently.  This method is called automatically when the
 * number of keys in the hashtable exceeds this hashtable"s capacity
 * and load factor.
 */
@SuppressWarnings("unchecked")
protected void rehash() {
    int oldCapacity = table.length;
    Entry[] oldMap = table;

    // overflow-conscious code
    int newCapacity = (oldCapacity << 1) + 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[] newMap = new Entry[newCapacity];

    modCount++;
    threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
    table = newMap;

    for (int i = oldCapacity ; i-- > 0 ;) {
        for (Entry old = (Entry)oldMap[i] ; old != null ; ) {
            Entry e = old;
            old = old.next;

            int index = (e.hash & 0x7FFFFFFF) % newCapacity;
            e.next = (Entry)newMap[index];
            newMap[index] = e;
        }
    }
}

hashtable的新容量是:2倍+1,即始终为奇数。不同于前2回讲过的hashmap中resize()则是2倍。why?我们知道“除2以外所有的素数都是奇数”,而当哈希表的大小为素数时,简单的取模哈希的结果分布更加均匀,从而降低哈希冲突。

“0x7FFFFFFF”即二进制的32个1,按位与运算后使得结果范围在区间[0,2147483647]内,可以理解为取正。

此外,for循环中的新旧数据迁移的5行代码也很经典。

 /**
 * Creates a shallow copy of this hashtable. All the structure of the
 * hashtable itself is copied, but the keys and values are not cloned.
 * This is a relatively expensive operation.
 *
 * @return  a clone of the hashtable
 */
public synchronized Object clone() {
    try {
        Hashtable t = (Hashtable)super.clone();
        t.table = new Entry[table.length];
        for (int i = table.length ; i-- > 0 ; ) {
            t.table[i] = (table[i] != null)
                ? (Entry) table[i].clone() : null;
        }
        t.keySet = null;
        t.entrySet = null;
        t.values = null;
        t.modCount = 0;
        return t;
    } catch (CloneNotSupportedException e) {
        // this shouldn"t happen, since we are Cloneable
        throw new InternalError(e);
    }
}

“shallow copy”一词成功引起了笔者注意。what is it?浅拷贝非java独有的概念,其他编程语言同样存在,如C#、C++、IOS、python等。与之对应的是深拷贝(deep copy)。两者的区别是:

对象的浅拷贝会对“主”对象进行拷贝,但不会复制主对象里面的对象。"里面的对象“会在原来的对象和它的副本之间共享。深拷贝是一个整个独立的对象拷贝。[参考文献2]

“I have a pen, I have a apple."(唱起来了) 我,笔,苹果是三个对象,我引用了笔和苹果,此时对我进行拷贝,效果如图:

public class Apple {
    String color;

    public String getColor() {
        return color;
    }

    public void setColor(String color) {
        this.color = color;
    } 
}

Apple apple = new Apple();
apple.setColor("red");

Hashtable ht = new Hashtable();
ht.put("apple", apple);
System.out.println(((Apple)ht.get("apple")).getColor());

Hashtable htc = (Hashtable) ht.clone();
System.out.println(((Apple)htc.get("apple")).getColor());

((Apple)htc.get("apple")).setColor("green");
System.out.println(((Apple)ht.get("apple")).getColor());
System.out.println(((Apple)htc.get("apple")).getColor());

//输出结果:
//red
//red
//green
//green
//浅拷贝的hashtable共用一个苹果
/**
 * Returns a string representation of this Hashtable object
 * in the form of a set of entries, enclosed in braces and separated
 * by the ASCII characters "" (comma and space). Each
 * entry is rendered as the key, an equals sign =, and the
 * associated element, where the toString method is used to
 * convert the key and element to strings.
 *
 * @return  a string representation of this hashtable
 */
public synchronized String toString() {
    int max = size() - 1;
    if (max == -1)
        return "{}";

    StringBuilder sb = new StringBuilder();
    Iterator> it = entrySet().iterator();

    sb.append("{");
    for (int i = 0; ; i++) {
        Map.Entry e = it.next();
        K key = e.getKey();
        V value = e.getValue();
        sb.append(key   == this ? "(this Map)" : key.toString());
        sb.append("=");
        sb.append(value == this ? "(this Map)" : value.toString());

        if (i == max)
            return sb.append("}").toString();
        sb.append(", ");
    }
}

"(this Map)",即,ht.put(ht, ht)将输出{(this Map)=(this Map)}。

还有同步处理用到的volatile关键字(各个线程在访问该关键字所修饰变量前必须从主存(共享内存)中读取该变量的值)、Collections.synchronizedSet()(创建同步的集合对象)有缘再续。

更多有意思的内容,欢迎访问笔者小站: rebey.cn

参考文献[推荐]:

1.HashMap和HashTable到底哪不同?,2016-07-05;

2.Java 中的浅拷贝与深拷贝(Shallow vs. Deep Copy in Java ),中英;

3.Java基础之volatile关键字,2016-07-18;

文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。

转载请注明本文地址:https://www.ucloud.cn/yun/67138.html

相关文章

  • java源码一带一路系列LinkedHashMap.afterNodeAccess()

    摘要:如今行至于此,当观赏一方。由于所返回的无执行意义。源码阅读总体门槛相对而言比,毕竟大多数底层都由实现了。比心可通过这篇文章理解创建一个实例过程图工作原理往期线路回顾源码一带一路系列之源码一带一路系列之源码一带一路系列之 本文以jdk1.8中LinkedHashMap.afterNodeAccess()方法为切入点,分析其中难理解、有价值的源码片段(类似源码查看是ctrl+鼠标左键的过程...

    levy9527 评论0 收藏0
  • java源码一带一路系列ArrayList

    摘要:一路至此,风景过半。与虽然名字各异,源码实现基本相同,除了增加了线程安全。同时注意溢出情况处理。同时增加了考虑并发问题。此外,源码中出现了大量泛型如。允许为非线程安全有序。 一路至此,风景过半。ArrayList与Vector虽然名字各异,源码实现基本相同,除了Vector增加了线程安全。所以作者建议我们在不需要线程安全的情况下尽量使用ArrayList。下面看看在ArrayList源...

    RebeccaZhong 评论0 收藏0
  • java源码一带一路系列HashSet、LinkedHashSet、TreeSet

    摘要:同样在源码的与分别见看到老朋友和。这样做可以降低性能消耗的同时,还可以减少序列化字节流的大小,从而减少网络开销框架中。使用了反射来寻找是否声明了这两个方法。十进制和,通过返回值能反应当前状态。 Map篇暂告段落,却并非离我们而去。这不在本篇中你就能经常见到她。HashSet、LinkedHashSet、TreeSet各自基于对应Map实现,各自源码内容较少,因此归纳为一篇。 HashS...

    UCloud 评论0 收藏0
  • java源码一带一路系列HashMap.compute()

    摘要:本篇涉及少许以下简称新特性,请驴友们系好安全带,准备开车。观光线路图是在中新增的一个方法,相对而言较为陌生。其作用是把的计算结果关联到上即返回值作为新。实际上,乃缩写,即二元函数之意类似。 本文以jdk1.8中HashMap.compute()方法为切入点,分析其中难理解、有价值的源码片段(类似源码查看是ctrl+鼠标左键的过程)。本篇涉及少许Java8(以下简称J8)新特性,请驴友们...

    wapeyang 评论0 收藏0
  • java源码一带一路系列HashMap.putAll()

    摘要:观光线路图将涉及到的源码全局变量哈希表初始化长度默认值是负载因子默认表示的填满程度。根据是否为零将原链表拆分成个链表,一部分仍保留在原链表中不需要移动,一部分移动到原索引的新链表中。 前言 本文以jdk1.8中HashMap.putAll()方法为切入点,分析其中难理解、有价值的源码片段(类似ctrl+鼠标左键查看的源码过程)。✈观光线路图:putAll() --> putMapEnt...

    chanjarster 评论0 收藏0

发表评论

0条评论

最新活动
阅读需要支付1元查看
<