首先来了解一下基本概念 所谓哈希表(Hash Table,又叫散列表),是存储键值对(Key-value)的表,之所以不叫它Map(键值对一起存储一般叫做Map),是因为它下面的特性:
它能把关键码(key)映射到表中的一个位置来直接访问,这样访问速度就非常快。其中的映射函数称为散列函数(Hash function)。
1) 对于关键字key, f(key)是其存储位置,f则是散列函数
2) 如果key1 != key2 但是 f(key1) == f(key2),这种现象称为冲突(collison)。冲突不可避免,这是因为key值无限而表容量总是有限(*见篇末思考题*)。我们追求的是对任意关键字,散列到表中的地址概率是相等的,这样的散列函数为均匀散列函数。
散列函数有多种
× 直接定址法:取关键字或关键字的某个线性函数值为散列地址。即H(key)=key或H(key) = a·key + b,其中a和b为常数(这种散列函数叫做自身函数)
× 数字分析法
× 平方取中法
× 折叠法
× 随机数法
× 除留余数法:取关键字被某个不大于散列表表长m的数p除后所得的余数为散列地址。即 H(key) = key MOD p, p<=m。不仅可以对关键字直接取模,也可在折叠、平方取中等运算之后取模。对p的选择很重要,一般取素数或m,若p选的不好,容易产生同义词。
可以想像,当表中的数据个数接近表的容量大小时,发生冲突的概率会明显增大,因此,在“数据个数/表容量”到达某个比例的时侯,需要扩大表的容量,这个比例称为
“装填因子”(load factor).
解决冲突主要有下面两类方法:
× 分离链接法,就是对hash到同一地址的不同元素,用链表连起来,也叫拉链法
× 开放定址法,如果地址有冲突,就在此地址附近找。包括线性探测法,平方探测法,双散列等
然后来看一下Java的Hashtable实现 java.util.Hashtable的本质是个数组,数组的元素是linked的键值对(单向链表)。
- private transient Entry[] table;
- private static class Entry<K,V> implements Map.Entry<K,V> {
- int hash;
- K key;
- V value;
- Entry<K,V> next;
- ...
- }
我们可以使用指定数组大小、装填因子的构造函数,也可以使用默认构造函数,默认数组的大小是11,装填因子是0.75.
- public Hashtable(int initialCapacity, float loadFactor) {
- ...
- }
- public Hashtable() {
- this(11, 0.75f);
- }
当要扩大数组时,大小变为oldCapacity * 2 + 1,当然这无法保证数组的大小总是素数。
来看下其中的元素插入的方法,put方法:
- public synchronized V put(K key, V value) {
-
- if (value == null) {
- throw new NullPointerException();
- }
-
-
- 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 old = e.value;
- e.value = value;
- return old;
- }
- }
- }
Java中Object类有几个方法,其中一个是hashCode(), 这说明Java中所有对象都具有这一方法,调用可以得到对象自身的hash码。对表的长度取余得址,并在冲突位置使用链表。
HashMap与Hashtable的功能几乎一样。但HashMap的的初始数组大小是16而不是11,当要扩大数组时,大小变为原来的2倍,默认的装填因子也是0.75. 其put方法如下,对hash值和index都有更改:
- public V put(K key, V value) {
- if (key == null)
- return putForNullKey(value);
- int hash = hash(key.hashCode());
- 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;
- }
-
-
-
-
-
-
-
-
-
- static int hash(int h) {
-
-
-
- h ^= (h >>> 20) ^ (h >>> 12);
- return h ^ (h >>> 7) ^ (h >>> 4);
- }
-
-
-
-
- static int indexFor(int h, int length) {
- return h & (length-1);
- }
再看看其它开源的Java库中的Hashtable 目前存在多个开源的Java Collection实现,各个目的不同,侧重点也不同。以下对开源框架中哈希表的分析主要从几个方面入手:默认装填因子和capacity扩展方式,散列函数以及解决冲突的方法。
1. Trove - Trove库提供一套高效的基础集合类。
gnu.trove.set.hash.THashMap的继承关系:THashMap -> TObjectHash -> THash,其内部的键和值使分别用2个数组表示。其解决冲突的方式采用开放寻址法,开放寻址法对空间要求较高,因此其默认装填因子load factor是0.5,而不是0.75. 下面看代码一步步解释:
默认初始化,装填因子0.5,数组大小始从素数中取,也就是始终是素数。
-
- public static final float DEFAULT_LOAD_FACTOR = 0.5f;
-
- protected int setUp( int initialCapacity ) {
- int capacity;
- capacity = PrimeFinder.nextPrime( initialCapacity );
- computeMaxSize( capacity );
- computeNextAutoCompactionAmount( initialCapacity );
- return capacity;
- }
然后看其put方法,insertKey(T key)是其散列算法,hash码对数组长度取余后,得到index,首先检查该位置是否被占用,如果被占用,使用双散列算法解决冲突,也就是代码中的insertKeyRehash()方法。
- public V put(K key, V value) {
-
- int index = insertKey(key);
- return doPut(value, index);
- }
-
-
- protected int insertKey(T key) {
- consumeFreeSlot = false;
-
- if (key == null)
- return insertKeyForNull();
-
- final int hash = hash(key) & 0x7fffffff;
- int index = hash % _set.length;
- Object cur = _set[index];
-
- if (cur == FREE) {
- consumeFreeSlot = true;
- _set[index] = key;
- return index;
- }
-
- if (cur == key || equals(key, cur)) {
- return -index - 1;
- }
-
- return insertKeyRehash(key, index, hash, cur);
- }
2. Javolution - 对实时、内置、高性能系统提供Java解决方案
Javolution中的哈希表是jvolution.util.FastMap, 其内部是双向链表,默认初始大小是16,扩展时变为2倍。并没有显式定义load factor, 从下面语句可以知道,其值为0.5
- if (map._entryCount + map._nullCount > (entries.length >> 1)) {
- map.resizeTable(_isShared);
- }
再看下put函数,比较惊人的是其index和slot的取得,完全是用hashkey移位的方式取得的,这样同时计算了index和避免了碰撞。
- private final Object put(Object key, Object value, int keyHash,
- boolean concurrent, boolean noReplace, boolean returnEntry) {
- final FastMap map = getSubMap(keyHash);
- final Entry[] entries = map._entries;
- final int mask = entries.length - 1;
- int slot = -1;
- for (int i = keyHash >> map._keyShift;; i++) {
- Entry entry = entries[i & mask];
- if (entry == null) {
- slot = slot < 0 ? i & mask : slot;
- break;
- } else if (entry == Entry.NULL) {
- slot = slot < 0 ? i & mask : slot;
- } else if ((key == entry._key) || ((keyHash == entry._keyHash) && (_isDirectKeyComparator ? key.equals(entry._key)
- : _keyComparator.areEqual(key, entry._key)))) {
- if (noReplace) {
- return returnEntry ? entry : entry._value;
- }
- Object prevValue = entry._value;
- entry._value = value;
- return returnEntry ? entry : prevValue;
- }
- }
- ...
- }
*思考题*
如果表容量无限,元素个数也无限,表是否必然能一一对应地包含所有元素?
相关推荐
Java哈希表性能优化
JAVA哈希表.pdf
java 实现常用数据结构(链表,集合,栈,哈希表,搜索,排序等).
哈希表(1).zip
哈希表java代码
哈希表 哈希表.java Java对哈希表的操作
Java数据结构 线性表,链表,哈希表是常用的数据结构,在进行Java开发时,JDK已经为我们提供了一系列相应的类来实现基本的数据结构
哈希表 哈希表_使用Java开发的哈希表_HashTable
主要介绍了哈希表HashMap的深入学习,哈希表是一种非常重要的数据结构,许多缓存技术(比如memcached)的核心其实就是在内存中维护一张大的哈希表,本文会对java集合框架中HashMap的实现原理进行讲解。感兴趣的话可以...
哈希表Java 用于学习目的的Java哈希表程序
数据结构学习笔记(5)——使用draw.io绘制的映射、哈希表和跳跃表图,详细绘制了映射、哈希表和跳跃表图,使用draw.io——免费开源的画图工具。
用java写的拉链法实现哈希表的建立,应用到类似于电话本查询的程序里,课程设计时候做的,所以不是很完美
哈希表经典讲解+各项优化+分析哈希表经典讲解+各项优化+分析哈希表经典讲解+各项优化+分析哈希表经典讲解+各项优化+分析哈希表经典讲解+各项优化+分析哈希表经典讲解+各项优化+分析哈希表经典讲解+各项优化+分析哈希...
数据结构(Java语言描述) 单元设计_单元8 哈希表.doc 学习资料 复习资料 教学资源
最近做项目需要用到哈希表,由于易语言没有原生的哈希表。在网上倒是有一些网友自己写的哈希表 但是都不是很满意。...本哈希类为模仿java中 jdk哈希表。只是处理冲突键时,一直使用的线性表。@5182235367。
Java中的哈希表
这个是java版的哈希表演示程序,里面用到的散列函数及处理冲突的方法都相对简单,但是可以加深大家对哈希表的认识。
讲解哈希函数,哈希表的原理以及常用运算。 是常用的数据结构
Java中哈希表(Hashtable)是如何实现的呢?Hashtable中有一个内部类Entry,用来保存单元数据,我们用来构建哈希表的每一个数据是Entry的一个实例。假设我们保存下面一组数据,第一列作为key, 第二列作为value。
哈希表的设计与实现。 有文档、源代码,数据结构的课程设计