文档章节

Java哈希表

秋风醉了
 秋风醉了
发布于 2014/09/19 16:58
字数 3303
阅读 513
收藏 1

Java哈希表

Java实现哈希表_哈希表使用链地址法解决哈希碰撞。

这篇文章就是来学习Java中哈希表实现过程的。简化java.util.Hashtable类,还原最真实的Hashtable。

Hashtable的内部存储结构

 

HashTable采用"拉链法"实现哈希表,它定义了几个重要的参数:table、count、threshold、loadFactor、modCount。

  • table:为一个Entry[]数组类型,Entry代表了“拉链”的节点,每一个Entry代表了一个键值对,哈希表的"key-value键值对"都是存储在Entry数组中的

  • count:HashTable的大小,注意这个大小并不是HashTable的容器大小,而是他所包含Entry键值对的数量。

  • threshold:Hashtable的阈值,用于判断是否需要调整Hashtable的容量。threshold的值="容量*加载因子"。

  • loadFactor:加载因子。

  • modCount:用来实现“fail-fast”机制的(也就是快速失败)。所谓快速失败就是在并发集合中,其进行迭代操作时,若有其他线程对其进行结构性的修改,这时迭代器会立马感知到,并且立即抛出ConcurrentModificationException异常,而不是等到迭代完成之后才告诉你(你已经出错了)。

 

Hashtable中具体的代码表示的数组

/**
* The hash table data.
*/
private transient Entry<?, ?>[] table;

正是这样的数据存储方式,才实现了哈希表具有较快(常量级)的查询速度,及相对较快的增删速度,所以很适合在海量数据的环境中使用。

如上图所示,使用一个长度为16的数组,数组元素存储的是链表的头结点。这是为了解决哈希碰撞而设计的一种数据结构。那么如何确定数组元素的下标呢?

在Hashtable类put方法中有一段这样的代码:(JDK1.8)‍‍

int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;

这段代码就是确定该元素在数组中的索引位置。

比如上述哈希表中,12%16=12,28%16=12,108%16=12,140%16=12。所以12、28、108以及140都存储在数组下标为12的位置。

Entry的定义如下,next属性指向下一个节点

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

    protected Entry(int hash, K key, V value, Entry<K, V> next) {
        this.hash = hash;
        this.key = key;
        this.value = value;
        this.next = next;
    }
    .........
    .........
}

 

哈希碰撞的解决方法

链地址法

如刚开始那幅图演示的那样的数据结构。数组元素保存链表的头结点,当哈希碰撞发生时,保存在头结点指向的链表中。

 

Java中的hashcode方法

实现哈希表,要涉及到hashcode方法。对于hashcode方法,在Object类中他是一个native方法。

public native int hashCode();

考虑一种情况,当向集合中插入对象时,如何判别在集合中是否已经存在该对象了?(注意:集合中不允许重复的元素存在)

也许大多数人都会想到调用equals方法来逐个进行比较,这个方法确实可行。但是如果集合中已经存在一万条数据或者更多的数据,如果采用equals方法去逐一比较,效率必然是一个问题。此时hashCode方法的作用就体现出来了,当集合要添加新的对象时,先调用这个对象的hashCode方法,得到对应的hashcode值,实际上在HashMap的具体实现中会用一个table保存已经存进去的对象的hashcode值,如果table中没有该hashcode值,它就可以直接存进去,不用再进行任何比较了;如果存在该hashcode值, 就调用它的equals方法与新元素进行比较,相同的话就不存了,不相同就散列其它的地址,所以这里存在一个冲突解决的问题,这样一来实际调用equals方法的次数就大大降低了,说通俗一点:Java中的hashCode方法就是根据一定的规则将与对象相关的信息(比如对象的存储地址,对象的字段等)映射成一个数值,这个数值称作为散列值。

以下代码是Hashtable中containsKey方法的实现,就是按照刚才讲的那个思路实现的:

public synchronized boolean containsKey(Object key) {
    Entry<?,?> tab[] = table;
    int hash = key.hashCode();
    int index = (hash & 0x7FFFFFFF) % tab.length;
    for (Entry<?,?> e = tab[index] ; e != null ; e = e.next) {
        if ((e.hash == hash) && e.key.equals(key)) {
            return true;
        }
    }
    return false;
}

Entry<?,?> e = tab[index]这小段代码就是根据hashcode计算出来的索引值直接得到的数组元素。

 

因为hashCode方法是native方法,那么这个native方法方法是如何实现的(hashCode方法不是简单的返回对象的内存地址)

不管懂不懂先看Hotspot虚拟机是如何实现的:

static inline intptr_t get_next_hash(Thread * Self, oop obj) {
  intptr_t value = 0 ;
  if (hashCode == 0) {
     // This form uses an unguarded global Park-Miller RNG,
     // so it's possible for two threads to race and generate the same RNG.
     // On MP system we'll have lots of RW access to a global, so the
     // mechanism induces lots of coherency traffic.
     value = os::random() ;
  } else
  if (hashCode == 1) {
     // This variation has the property of being stable (idempotent)
     // between STW operations.  This can be useful in some of the 1-0
     // synchronization schemes.
     intptr_t addrBits = intptr_t(obj) >> 3 ;
     value = addrBits ^ (addrBits >> 5) ^ GVars.stwRandom ;
  } else
  if (hashCode == 2) {
     value = 1 ;            // for sensitivity testing
  } else
  if (hashCode == 3) {
     value = ++GVars.hcSequence ;
  } else
  if (hashCode == 4) {
     value = intptr_t(obj) ;
  } else {
     // Marsaglia's xor-shift scheme with thread-specific state
     // This is probably the best overall implementation -- we'll
     // likely make this the default in future releases.
     unsigned t = Self->_hashStateX ;
     t ^= (t << 11) ;
     Self->_hashStateX = Self->_hashStateY ;
     Self->_hashStateY = Self->_hashStateZ ;
     Self->_hashStateZ = Self->_hashStateW ;
     unsigned v = Self->_hashStateW ;
     v = (v ^ (v >> 19)) ^ (t ^ (t >> 8)) ;
     Self->_hashStateW = v ;
     value = v ;
  }
 
  value &= markOopDesc::hash_mask;
  if (value == 0) value = 0xBAD ;
  assert (value != markOopDesc::no_hash, "invariant") ;
  TEVENT (hashCode: GENERATE) ;
  return value;
}

该实现位于hotspot/src/share/vm/runtime/synchronizer.cpp文件下。

因此有人会说,可以直接根据hashcode值判断两个对象是否相等吗?肯定是不可以的,因为不同的对象可能会生成相同的hashcode值。虽然不能根据hashcode值判断两个对象是否相等,但是可以直接根据hashcode值判断两个对象不等,如果两个对象的hashcode值不等,则必定是两个不同的对象。如果要判断两个对象是否真正相等,必须通过equals方法。

 

关于hashCode()和equals()方法

 下面这段话摘自Effective Java一书:

  • 在程序执行期间,只要equals方法的比较操作用到的信息没有被修改,那么对这同一个对象调用多次,hashCode方法必须始终如一地返回同一个整数。

  • 如果两个对象根据equals方法比较是相等的,那么调用两个对象的hashCode方法必须返回相同的整数结果。

  • 如果两个对象根据equals方法比较是不等的,则hashCode方法不一定得返回不同的整数。

  对于第二条和第三条很好理解,但是第一条,很多时候就会忽略。在《Java编程思想》一书中的P495页也有同第一条类似的一段话:

“设计hashCode()时最重要的因素就是:无论何时,对同一个对象调用hashCode()都应该产生同样的值。如果在讲一个对象用put()添加进HashMap时产生一个hashCdoe值,而用get()取出时却产生了另一个hashCode值,那么就无法获取该对象了。所以如果你的hashCode方法依赖于对象中易变的数据,用户就要当心了,因为此数据发生变化时,hashCode()方法就会生成一个不同的散列码”

 

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);
}

/**
 * Constructs a new, empty hashtable with the specified initial capacity
 * and default load factor (0.75).
 *
 * @param     initialCapacity   the initial capacity of the hashtable.
 * @exception IllegalArgumentException if the initial capacity is less
 *              than zero.
 */
public Hashtable(int initialCapacity) {
    this(initialCapacity, 0.75f);
}

/**
 * Constructs a new, empty hashtable with a default initial capacity (11)
 * and load factor (0.75).
 */
public Hashtable() {
    this(11, 0.75f);
}

主要看懂两个属性:

  • threshold:Hashtable的阈值,用于判断是否需要调整Hashtable的容量。threshold的值="容量*加载因子"
  • loadFactor:加载因子

threshold = (int)Math.min(initialCapacity * loadFactor, MAX_ARRAY_SIZE + 1);

 

Hashtable中添加k-v值对最终是通过addEntry方法添加的,看该方法实现:

private void addEntry(int hash, K key, V value, int index) {
    modCount++;

    Entry<?,?> tab[] = table;
    if (count >= threshold) {
        // Rehash the table if the threshold is exceeded
        rehash();

        tab = table;
        hash = key.hashCode();
        index = (hash & 0x7FFFFFFF) % tab.length;
    }

    // Creates the new entry.
    @SuppressWarnings("unchecked")
    Entry<K,V> e = (Entry<K,V>) tab[index];
    tab[index] = new Entry<>(hash, key, value, e);
    count++;
}

通过这段代码你可以看到阀值的作用了吧。当count大于阀值时,要重新进行hash,重新确定Hashtable的大小。

 

自定义Hashtable的实现

以上分析了类库中Hashtable的实现过程,那么我试着自己实现一个简单的Hashtable,

就是为了把Hashtable的其他细节去掉,主要保留其数据结构和解决哈希碰撞。

贴代码:大部分代码来源自类库中Hashtable的代码,加了详细的注释

package hash;

import java.util.Objects;

/**
 * Created with IntelliJ IDEA.
 * User: ASUS
 * Date: 14-9-18
 * Time: 下午5:37
 * To change this template use File | Settings | File Templates.
 */
public class CustomHashtable<K, V> {


    /**
     * The hash table data.
     */
    private Entry<K, V>[] table;

    /**
     * The total number of entries in the hash table.
     */
    private int count;

    /**
     * The table is rehashed when its size exceeds this threshold.  (The
     * value of this field is (int)(capacity * loadFactor).)
     *
     * @serial
     */
    private int threshold;

    /**
     * The load factor for the hashtable.
     *
     * @serial
     */
    private float loadFactor;


    /**
     * 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;

    /**
     * Hashtable bucket collision list entry
     */
    private static class Entry<K, V> {
        int hash;
        K key;
        V value;
        Entry next;

        public Entry() {
        }

        public Entry(int hash, K key, V value, Entry next) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }

        public K getKey() {
            return key;
        }

        public V getValue() {
            return value;
        }

        public V setValue(V value) {
            if (value == null)
                throw new NullPointerException();

            V oldValue = this.value;
            this.value = value;
            return oldValue;
        }

        public boolean equals(Object o) {
            if (!(o instanceof Entry))
                return false;
            Entry<K, V> e = (Entry<K, V>) o;

            return (key == null ? e.getKey() == null : key.equals(e.getKey())) &&
                    (value == null ? e.getValue() == null : value.equals(e.getValue()));
        }

        public int hashCode() {
            return hash ^ Objects.hashCode(value);
        }

        public String toString() {
            return key.toString() + "=" + value.toString();
        }
    }


    /**
     * Constructs a new, empty hashtable with the specified initial
     * capacity and the specified load factor.
     *
     * @param initialCapacity the initial capacity of the hashtable.
     * @param loadFactor      the load factor of the hashtable.
     * @throws IllegalArgumentException if the initial capacity is less
     *                                  than zero, or if the load factor is nonpositive.
     */
    public CustomHashtable(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);
    }

    /**
     * Constructs a new, empty hashtable with the specified initial capacity
     * and default load factor (0.75).
     *
     * @param initialCapacity the initial capacity of the hashtable.
     * @throws IllegalArgumentException if the initial capacity is less
     *                                  than zero.
     */
    public CustomHashtable(int initialCapacity) {
        this(initialCapacity, 0.75f);
    }

    /**
     * Constructs a new, empty hashtable with a default initial capacity (11)
     * and load factor (0.75).
     */
    public CustomHashtable() {
        this(11, 0.75f);
    }

    /**
     * Returns the number of keys in this hashtable.
     *
     * @return the number of keys in this hashtable.
     */
    public synchronized int size() {
        return count;
    }

    /**
     * value值不能为空
     *
     * @param key
     * @param value
     * @return
     */
    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;
        @SuppressWarnings("unchecked")
        Entry<K, V> entry = (Entry<K, V>) tab[index];
        //当put元素时,如果该索引位置上存在Entry元素,
        //则则遍历该Entry链表
        for (; entry != null; entry = entry.next) {
            if ((entry.hash == hash) && entry.key.equals(key)) {
                V old = entry.value;
                entry.value = value;  //覆盖原来的value
                return old;
            }
        }
        // 当两个不同的key计算出相同的哈希索引,则会发生碰撞。
        // 发生碰撞后,遍历当前索引位置上的entry链表,如果entry节点中key的哈希值想等并且key相等,
        // 就会使用新的value覆盖原来的value。
        // 如果在该索引上没有元素存在,那么添加Entry
        addEntry(hash, key, value, index);
        return null;
    }

    /**
     * @param key
     * @return
     */
    public synchronized V get(Object key) {
        Entry<?, ?> tab[] = table;
        int hash = key.hashCode();
        int index = (hash & 0x7FFFFFFF) % tab.length;
        for (Entry<?, ?> e = tab[index]; e != null; e = e.next) {
            if ((e.hash == hash) && e.key.equals(key)) {
                return (V) e.value;
            }
        }
        return null;
    }

    /**
     * 增加元素
     *
     * @param hash
     * @param key
     * @param value
     * @param index
     */
    private void addEntry(int hash, K key, V value, int index) {

        Entry<?, ?> tab[] = table;

        //当哈希表中元素的数量大于阀值时,重新设置哈希表的大小
        if (count >= threshold) {
            // Rehash the table if the threshold is exceeded
            rehash();

            tab = table;
            hash = key.hashCode();
            index = (hash & 0x7FFFFFFF) % tab.length;
        }

        // Creates the new entry.
        @SuppressWarnings("unchecked")
        Entry<K, V> e = (Entry<K, V>) tab[index];   //取得哈希索引上的元素,是entry链表上的头结点
        // 把新的节点插入到链表的头结点位置
        tab[index] = new Entry<K, V>(hash, key, value, e);
        count++;
    }


    /**
     * 重新分配哈希表内部数组的大小
     */
    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];   //初始化新的数组空间,存储Entry

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

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

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

    /**
     * @param arg
     */
    public static void main(String arg[]) {
        CustomHashtable<String, String> hashtable = new CustomHashtable<String, String>();
        for (int i = 0; i < 9; i++) {
            hashtable.put("lyx" + i, "lyx" + i);
        }

        hashtable.put("lyx0", "aaaaaaaaaaaaaaaaaaaaa");
        hashtable.put("lyx0", "aaaaaaaaaaaaaaaaaaaaa");
        hashtable.put("lyx0", "aaaaaaaaaaaaaaaaaaaaa");
        hashtable.put("lyx0", "aabbccdd");

        System.out.println(hashtable.get("lyx0"));
        System.out.println(hashtable.get("lyx1"));
        System.out.println(hashtable.get("lyx2"));
        System.out.println(hashtable.get("lyx3"));
    }
}

参考链接:

http://www.cnblogs.com/dolphin0520/p/3681042.html

http://www.cnblogs.com/dolphin0520/archive/2012/09/28/2700000.html

http://www.cnblogs.com/jiewei915/archive/2010/08/09/1796042.html

http://www.cnblogs.com/chenssy/p/3643886.html

===========END===========

© 著作权归作者所有

下一篇: MySQL使用外键
秋风醉了
粉丝 252
博文 532
码字总数 405694
作品 0
朝阳
程序员
私信 提问
深入谈谈String.intern()在JVM的实现

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/wangyangzhizhou/article/details/79860622 前言 String 类的方法可能大家比较少用也比较陌生,虽然实际项目中...

超人汪小建(seaboat)
2018/04/09
0
0
可视化的数据结构和算法

还记得之前发布过的那个关于可视化排序的文章吗?在网上又看到了一个旧金山大学David Galles做的各种可视化的数据结构和基本算法的主页,网址在这里,大家可以看看。我把这个页面的目录列在下...

戴威
2011/05/12
1K
5
Java Hashtable 涉及的数据结构、实现及冲突处理

Hashtable 提供的功能 Hashtable是一个线程安全的Map,其线程安全是通过在各个方法上加上synchronized关键字实现的,即:该类只能被一个线程所使用,其他调用该类时会阻塞等待; 实现了哈希表...

666B
2018/11/28
11
0
Java拾遗:002 - HashMap源码解读

哈希表 散列表(Hash Table,也叫哈希表),是根据关键码值(Key value)而直接进行访问的数据结构。这种数据结构在不考虑哈希碰撞的条件下,有前着O(1)的时间复杂度,所以效率非常高。Java中H...

一别丶经年
2018/08/03
13
0
Java数据结构知多少?java入门学习

  初学java时,我们会了解到Java工具包提供了强大的数据结构,那么Java的数据结构都有哪几种呢?   一、枚举(Enumeration)接口虽然它本身不属于数据结构,但它在其他数据结构的范畴里应用很...

老男孩Linux培训
2018/07/09
6
1

没有更多内容

加载失败,请刷新页面

加载更多

关于谷歌浏览器崩溃,打不开任何界面

首先:谷歌浏览器右键打开属性,在箭头所指的位置复制粘贴 -no-sandbox。(需要空一格再写入 -no-sandbox) 其次:你打开谷歌浏览器可以看到如下提醒,提醒你,稳定性和安全性会有所下降,但...

Raphael98
17分钟前
2
0
java 删除文件夹下的文件

/** * 删除已经下载过的文件 * @param path * @return */ @ApiOperation(value = "删除已经下载过的Excel",httpMethod="",notes="") @GetMapping("/deleteExcel") public Object downLoad(@......

简小姐
17分钟前
3
0
如何安装GMP,MPFR,MPC,ELF,无需共享库?

如何使用当前版本, 使用正确版本的依赖关系,不使用包管理器(如yum,rpm,apt,dpkg)并且不使用共享库,来逐块安装GCC(GNU编译器集合)? 典型的开发人员可能希望以典型的方式安装GCC,使...

mskk
21分钟前
2
0
Rancher + VMware PKS实现全球数百站点的边缘K8S集群管理

Sovereign Systems是一家成立于2007年的技术咨询公司,帮助客户将传统数据中心技术和应用程序转换为更高效的、基于云的技术平台,以更好地应对业务挑战。曾连续3年提名CRN,并且在2012年到2...

RancherLabs
26分钟前
2
0
docker修改log-driver后启动失败问题解决

vi /etc/sysconfig/docker 去掉--log-driver=journald 重启docker,重新run一个容器

abowu
27分钟前
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部