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

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

 1public Hashtable(int initialCapacity, float loadFactor) {
 2 if (initialCapacity < 0)
 3     throw new IllegalArgumentException("Illegal Capacity: "+
 4                                               initialCapacity);
 5        if (loadFactor <= 0 || Float.isNaN(loadFactor))
 6            throw new IllegalArgumentException("Illegal Load: "+loadFactor);
 7        if (initialCapacity==0)
 8            initialCapacity = 1;
 9 this.loadFactor = loadFactor;
10 table = new Entry[initialCapacity];
11 threshold = (int)(initialCapacity * loadFactor);
12    }

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

1private static class Entry<K,V> implements Map.Entry<K,V> {
2            int hash;
3            K key;
4            V value;
5            Entry<K,V> next;
6}

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

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

 1public synchronized V put(K key, V value) {
 2 // Make sure the value is not null
 3 if (value == null) {
 4     throw new NullPointerException();
 5 }
 6 // Makes sure the key is not already in the hashtable.
 7 Entry tab[] = table;
 8 int hash = key.hashCode();
 9 int index = (hash & 0x7FFFFFFF) % tab.length;
10 for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {
11     if ((e.hash == hash) && e.key.equals(key)) {
12  V ld = e.value;
13  e.value = value;
14  return old;
15     }
16 }
17 modCount++;
18 if (count >= threshold) {
19     // Rehash the table if the threshold is exceeded
20     rehash();
21            tab = table;
22            index = (hash & 0x7FFFFFFF) % tab.length;
23 }
24 // Creates the new entry.
25 Entry<K,V> e = tab[index];
26 tab[index] = new Entry<K,V>(hash, key, value, e);
27 count++;
28 return null;
29    }

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

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

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

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

三、get(Object),获得

 1public synchronized V get(Object key) {
 2 Entry tab[] = table;
 3 int hash = key.hashCode();
 4 int index = (hash & 0x7FFFFFFF) % tab.length;
 5 for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {
 6     if ((e.hash == hash) && e.key.equals(key)) {
 7  return e.value;
 8     }
 9 }
10 return null;
11    }

这个就很好理解了 int index = (hash & 0x7FFFFFFF) % tab.length;
获得队列名称:

1for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {
2     if ((e.hash == hash) && e.key.equals(key)) {
3  return e.value;
4     }
5 }

在该队里面遍历,根据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://strikefreedom.top/java-hashmap-hashtable

关于留言和评论

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