文章 56
评论 98
浏览 271517
java之hashtable和hashmap

java之hashtable和hashmap

hashtable 和 hashmap 是 Java 里面常见的容器类,是 Java.uitl 包下面的类,那么 Hashtable 和 Hashmap 是怎么实现 hash 键值对配对的呢,我们看看 jdk 里面的源码,分析下 Hashtable 的构造方法,put(K, V)加入方法和 get(Object)方法就大概明白了。

一、Hashtable 的构造方法:Hashtable(int initialCapacity, float loadFactor)

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)(initialCapacity * loadFactor);
    }

这个里面没有什么好说的,要注意的是 table 一个是实体数组,输入的 initialCapacity 表示这个数组的大小,而 threshold 是一个 int 值,其中 loadFactor 默认是 0.75,就是说明,当 table 里面的值到 75% 的阀值后,快要填满数组了,就会自动双倍扩大数字容量。
而 Entry<K,V> 来自于:

private static class Entry<K,V> implements Map.Entry<K,V> {
            int hash;
            K key;
            V value;
            Entry<K,V> next;
}

是一个单向链表
hashtable-entry
上图就是 Hashtable 的表。

二、put(K, V)加入方法

 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 = key.hashCode();
 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 ld = e.value;
  e.value = value;
  return old;
     }
 }
 modCount++;
 if (count >= threshold) {
     // Rehash the table if the threshold is exceeded
     rehash();
            tab = table;
            index = (hash & 0x7FFFFFFF) % tab.length;
 }
 // Creates the new entry.
 Entry<K,V> e = tab[index];
 tab[index] = new Entry<K,V>(hash, key, value, e);
 count++;
 return null;
    }

这段源码看起来很长,其实只需要注意三点就可以了:

  1. index,index 是键值的 hashcode 和 0x7FFFFFFF 的&运算,然后根据数组长度求余值。这样可以定出所在队列名称;
  2. jdk 源码
for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {
     if ((e.hash == hash) && e.key.equals(key)) {
  V ld = e.value;
  e.value = value;
  return old;
     }
 }

for 语句里面是让 e 在 tab 某个队列名为 index 单项链表里面遍历,第几个单项链表的定义由 index 定义,看看该队列是否已经有同样的值,如果有,就返回该值。

  1. 如果没有,则加入
 Entry<K,V> e = tab[index];
 tab[index] = new Entry<K,V>(hash, key, value, e);

三、get(Object),获得

 public synchronized V get(Object key) {
 Entry tab[] = table;
 int hash = key.hashCode();
 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)) {
  return e.value;
     }
 }
 return null;
    }

这个就很好理解了 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)) {
  return e.value;
     }
 }

在该队里面遍历,根据 hash 值获得具体值。

总结下,一个是根据 index 确定队列,在由 hash 值获得具体元素值。

看完了 hashtable, 我们在来看看 hashMap
hashMap 可以算作是 hashtable 的升级版本, 最早从 1.2 开始有的。

但是, 两者之间最主要的不同有两点:
第一是 hashMap 的读写是 unsynchronized, 在多线程的环境中要注意使用,而 hashtable 是 synchronized 的
这两者的不同是通过在读写方法上加 synchronized 关键字来实现的。

第二个不同是 hashMap 可以放空值, 而 hashtable 就会报错。

HashMap 的工作原理:

HashMap 基于 hashing 原理,我们通过 put()和 get()方法储存和获取对象。当我们将键值对传递给 put()方法时,它调用键对象的 hashCode()方法来计算 hashcode,让后找到 bucket 位置来储存值对象。当获取对象时,通过键对象的 equals()方法找到正确的键值对,然后返回值对象。HashMap 使用链表来解决碰撞问题,当发生碰撞了,对象将会储存在链表的下一个节点中。 HashMap 在每个链表节点中储存键值对对象。
当两个不同的键对象的 hashcode 相同时会发生什么? 它们会储存在同一个 bucket 位置的链表中。键对象的 equals()方法用来找到键值对。


微信公众号

潘建锋

关于版权和转载

本文由 潘建锋 创作,采用 署名 4.0 国际 (CC BY 4.0) 国际许可协议进行授权。
本站文章除注明转载/出处外,均为本站原创或翻译,转载时请务必署名,否则,本人将保留一切追究责任的权利。
署名 4.0 国际 (CC BY 4.0)

转载规范

标题:java之hashtable和hashmap
作者:潘建锋
原文:https://taohuawu.club/java-hashmap-hashtable

关于留言和评论

如果您对本文《java之hashtable和hashmap》的内容有任何疑问、补充或纠错,欢迎在下面的评论系统中留言,与作者一起交流进步,谢谢!(~ ̄▽ ̄)~

鲜衣怒马提银枪,一日看尽长安花,此间少年。