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来自于:

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

是一个单向链表

上图就是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()方法用来找到键值对。

原文发布于微信公众号 - 且拭青锋(just_wipe_sword)

原文发表时间:2018-05-16

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏软件开发 -- 分享 互助 成长

C++ STL之排序算法

排序算法和查找算法差不多,也涉及到迭代器区间问题,关于该问题的注意事项就不在啰嗦了 一、全部排序sort、stable_sort sort是一种不稳定排序,使用...

2025
来自专栏拭心的安卓进阶之路

Java 集合深入理解(13):Stack 栈

今天心情不错,再来一篇 Stack ! 数据结构中的 栈 数据结构中,栈是一种线性数据结构,遵从 LIFO(后进先出)的操作顺序,所有操作都是在顶部进行 ...

21510
来自专栏Java帮帮-微信公众号-技术文章全总结

【编程题】Java编程题一(10道)

【编程题】Java编程题一(10道) 【程序1】 题目:古典问题:有一对兔子,从出生后第3个月起每个月都生一对兔子,小兔子长到第三个月后每个月又生一对兔子,...

4548
来自专栏Java爬坑系列

【Java入门提高篇】Day33 Java容器类详解(十五)PriorityQueue详解

 今天要介绍的是基础容器类(为了与并发容器类区分开来而命名的名字)中的另一个成员——PriorityQueue,它的大名叫做优先级队列,想必即使没有用过也该有所...

1271
来自专栏机器学习与自然语言处理

用只含一个链域的节点实现循环链表的双向遍历

通常来说,要实现循环双向链表,每个节点需要有两个链域:前驱和后继。现在的问题是:如何设计一种环形表,使表的每个结点只包含一个链域而又能够有效地对其进行两个方向的...

2135
来自专栏mySoul

设计模式 里氏替换原则

在场景中,三毛需要什么枪支,就直接new 出一个枪支即可,然后其内通过抽象类获取到对象,然后对齐进行修饰

1246
来自专栏java达人

数字的陷阱

Java中对数字的处理,如四舍五入,如加减乘除,貌似是一个很基础很简单的知识点,但是如果你没有对他进行充分了解,很容易掉进它的陷阱里。 1、浮点数运算 先来看一...

1918
来自专栏desperate633

HashMap实现原理分析(Java源码剖析)内部实现存储结构-字段功能实现-方法Map中各实现类的总结小结

HashMap是Java程序员使用频率最高的用于映射(键值对)处理的数据类型。随着JDK(Java Developmet Kit)版本的更新,JDK1.8对Ha...

922
来自专栏恰童鞋骚年

数据结构基础温故-1.线性表(中)

在上一篇中,我们学习了线性表最基础的表现形式-顺序表,但是其存在一定缺点:必须占用一整块事先分配好的存储空间,在插入和删除操作上需要移动大量元素(即操作不方便)...

992
来自专栏码匠的流水账

聊聊flink的OperatorStateBackend

flink-runtime_2.11-1.7.0-sources.jar!/org/apache/flink/runtime/state/OperatorSta...

2582

扫码关注云+社区

领取腾讯云代金券