Java数据结构源码分析-HashTable

电玩女神 2022-08-23 01:22 324阅读 0赞

## 1.HashTable ##

HashTable同HashMap在数据结构的层面上是一致的，同时通过数组+链表的形式来存储数据。  
![这里写图片描述][u_2905135965_2708170433_fm_21_gp_0.jpg]  
其方法的功能和实现方式也基本一致。  
就不在此处赘述，如果要详细了解可以参看HashMap的源码分析：  
[http://blog.csdn.net/cweeyii/article/details/51583154][http_blog.csdn.net_cweeyii_article_details_51583154]  
下面我们给出下几个重要方法的对比：

//HashMap的Put方法
    public V put(K key, V value) {
            if (table == EMPTY_TABLE) {
                inflateTable(threshold);
            }
            if (key == null)
                return putForNullKey(value);
            int hash = hash(key);
            int i = indexFor(hash, table.length);
            for (Entry<K,V> e = table[i]; e != null; e = e.next) {
                Object k;
                if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                    V oldValue = e.value;
                    e.value = value;
                    e.recordAccess(this);
                    return oldValue;
                }
            }
    
            modCount++;
            addEntry(hash, key, value, i);
            return null;
        }
    //HashTable的Put方法
    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);
            int index = (hash & 0x7FFFFFFF) % tab.length;
            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;
        }
    //HashMap的构造方法
    public HashMap(int initialCapacity, float loadFactor) {
            if (initialCapacity < 0)
                throw new IllegalArgumentException("Illegal initial capacity: " +
                                                   initialCapacity);
            if (initialCapacity > MAXIMUM_CAPACITY)
                initialCapacity = MAXIMUM_CAPACITY;
            if (loadFactor <= 0 || Float.isNaN(loadFactor))
                throw new IllegalArgumentException("Illegal load factor: " +
                                                   loadFactor);
    
            this.loadFactor = loadFactor;
            threshold = initialCapacity;
            init();
        }
    //HashTable的构造方法：
    public Hashtable(int initialCapacity, float loadFactor) {
            if (initialCapacity < 0)
                throw new IllegalArgumentException("Illegal Capacity: "+
                                                   initialCapacity);
            if (loadFactor <= 0 || Float.isNaN(loadFactor))
                throw new IllegalArgumentException("Illegal Load: "+loadFactor);
    
            if (initialCapacity==0)
                initialCapacity = 1;
            this.loadFactor = loadFactor;
            table = new Entry[initialCapacity];
            threshold = (int)Math.min(initialCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
            initHashSeedAsNeeded(initialCapacity);
        }

## 2.HashMap和HashTable异同 ##

1.  HashMap构造时，并不分配table数组的内存空间，其实在第一次调用put方法时分配，并且其分配的空间是2的幂次大小，默认为16。 而HashTable在构造时分配table数据的内存空间，默认大小为11
2.  在继承层次上，HashMap是Map接口的一个实现，而HashTable是Dictionary的一个子类。其使用上这个并不存在太大区别
3.  HashMap的所有方法是非同步的方法，因此在不考虑线程间的共享的情况下，其速度更快。而HashTable里所有方法都是基于对象级别同步的，因此其是线程安全的。对于线程安全的结构HashMap提供了一个ConcurrentHashMap的选择，其实现原理比HashTable更加优异，这也是导致HashTable已经几乎不被人使用的原因。
4.  HashMap可以将空值作为一个表的条目的key或者value,HashMap中由于键不能重复，因此只有一条记录的Key可以是空值，而value可以有多个为空，但HashTable不允许null值(键与值均不行)
5.  内存扩容时采取的方式也不同，Hashtable采用的是2\*old+1,而HashMap是2\*old
6.  哈希值的计算方法不同，Hashtable直接使用的是对象的hashCode,而HashMap则是在对象的hashCode的基础上还进行了一些变化

## 3.总结 ##

1.由于HashMap系列具有：非线程安全的HashMap和线程安全的ConcurrentHashMap，因此可以完全忘记HashTable类的存在  
2.HashTable和HashMap的区别一直是各种面试时考察的内容：主要记住第二下节异同中的： 3、4就行了，其他可以了解

[u_2905135965_2708170433_fm_21_gp_0.jpg]: http://img4.imgtn.bdimg.com/it/u=2905135965,2708170433&fm=21&gp=0.jpg
[http_blog.csdn.net_cweeyii_article_details_51583154]: http://blog.csdn.net/cweeyii/article/details/51583154