- 浏览: 339093 次
- 性别:
- 来自: 大西洋底
文章分类
最新评论
-
jfztaq:
问题果然解决了,太感谢了
Chrome经常性的“喔唷,崩溃了”问题 -
saintor:
因为不是每个subclass都执行Cloneable吧。
Java Object类的方法们 -
337240552:
写的不错 这个东西晕死一堆人。
对JavaScript中原型的理解 -
liang86liang:
jkleeo 写道很深奥啊.
C/CPP只有在大学的时候听说过 ...
Windows下用Eclipse搭建C/C++开发环境 -
ahong520:
看来你也是四国军棋爱好者,啥时候切磋一下
四国军棋游戏V0.3.5(未完成)
首先来了解一下基本概念
所谓哈希表(Hash Table,又叫散列表),是存储键值对(Key-value)的表,它有下面的特性:它能把关键码(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的键值对(单向链表)。
我们可以使用指定数组大小、装填因子的构造函数,也可以使用默认构造函数,默认数组的大小是11,装填因子是0.75.
当要扩大数组时,大小变为oldCapacity * 2 + 1,当然这无法保证数组的大小总是素数。
来看下其中的元素插入的方法,put方法:
Java中Object类有几个方法,其中一个是hashCode(), 这说明Java中所有对象都具有这一方法,调用可以得到对象自身的hash码。对表的长度取余得址,并在冲突位置使用链表。
HashMap与Hashtable的功能几乎一样。但HashMap的的初始数组大小是16而不是11,当要扩大数组时,大小变为原来的2倍,默认的装填因子也是0.75. 其put方法如下,对hash值和index都有更改:
再看看其它开源的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,数组大小始从素数中取,也就是始终是素数。
然后看其put方法,insertKey(T key)是其散列算法,hash码对数组长度取余后,得到index,首先检查该位置是否被占用,如果被占用,使用双散列算法解决冲突,也就是代码中的insertKeyRehash()方法。
2. Javolution - 对实时、内置、高性能系统提供Java解决方案
Javolution中的哈希表是jvolution.util.FastMap, 其内部是双向链表,默认初始大小是16,扩展时变为2倍。并没有显式定义load factor, 从下面语句可以知道,其值为0.5
再看下put函数,比较惊人的是其index和slot的取得,完全是用hashkey移位的方式取得的,这样同时计算了index和避免了碰撞。
*思考题*
如果表容量无限,元素个数也无限,表是否必然能一一对应地包含所有元素?
所谓哈希表(Hash Table,又叫散列表),是存储键值对(Key-value)的表,它有下面的特性:它能把关键码(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; // Entry数组
private static class Entry<K,V> implements Map.Entry<K,V> { int hash; K key; V value; Entry<K,V> next; // Entry此处表明是个单链表 ... }
我们可以使用指定数组大小、装填因子的构造函数,也可以使用默认构造函数,默认数组的大小是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) { // 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 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; } /** * Applies a supplemental hash function to a given hashCode, which * defends against poor quality hash functions. This is critical * because HashMap uses power-of-two length hash tables, that * otherwise encounter collisions for hashCodes that do not differ * in lower bits. Note: Null keys always map to hash 0, thus index 0. */ static int hash(int h) { // This function ensures that hashCodes that differ only by // constant multiples at each bit position have a bounded // number of collisions (approximately 8 at default load factor). h ^= (h >>> 20) ^ (h >>> 12); return h ^ (h >>> 7) ^ (h >>> 4); } /** * Returns index for hash code h. */ 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,数组大小始从素数中取,也就是始终是素数。
/** the load above which rehashing occurs. */ 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) { // insertKey() inserts the key if a slot if found and returns the index 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; // insert value return index; // empty, all done } if (cur == key || equals(key, cur)) { return -index - 1; // already stored } 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)) { // Table more than half empty. 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; // Atomic. 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; } } ... }
*思考题*
如果表容量无限,元素个数也无限,表是否必然能一一对应地包含所有元素?
发表评论
-
文件分割与合并
2020-03-19 20:59 228package com.test.filestool; ... -
盒子里面另一个是红球的概率问题
2019-05-08 09:27 710问题如下:引用有三个盒子,其中一个里面是两个红球,一个里面是两 ... -
Mac OS X 下运行Java standalone 连接 Notes
2017-11-27 12:32 745Mac OS X 下运行Java standalone 连接 ... -
随机密码生成
2015-09-10 10:19 743import java.util.Random; p ... -
Java 处理mail subject
2015-06-15 21:16 1038对于mail subject 前面烦人的各种Re: 或Fw: ... -
有趣的“生命游戏”
2013-04-04 10:56 1005“生命游戏” 本世纪70年代,人们曾疯魔一种被称作“生命游戏” ... -
有趣的统计英文单词频率的例子
2013-03-02 00:22 1921统计一篇英文文档或一本小说中单词出现的次数,下面代码使用的是英 ... -
有趣的统计英文字母频率的例子
2013-03-01 01:13 1327统计的是英文版"悲惨世界",代码如下,使用 ... -
有趣的将一个十进制整数转换成二进制输出的算法
2013-02-27 00:20 1310原题是将一个十进制整数转换成二进制输出。 分析:任何数可以表 ... -
统一批量修改照片名字
2012-09-01 14:00 2885在给小宝拍的照片中,有我手机拍的,有媳妇手机拍的,还有相机拍的 ... -
关于Java的UUID
2012-08-30 18:40 8280UUID或者UNID或者UID,是一个统一唯一标识,可以用来标 ... -
关于Java中的哈希表
2012-07-27 10:01 1关于Java中的哈希表首先 ... -
关于Java的“浅拷贝”和“深拷贝” (clone method)
2012-07-24 14:31 1262这是关于Java的clone, 一些知道的和不知道的。 1. ... -
从某网站下载MP3的例子
2012-05-29 23:14 1345从某网站下载MP3的例子。为安全起见,将网站信息匿了。 ... -
统计项目中Java文件数和Java代码行数
2010-12-25 11:51 6435其实就是使用递归遍历目录下所有文件 import jav ... -
Java循环内goto语句的替代方案
2010-12-12 23:04 3209众所周知,Java虚拟机根本没有实现goto关键字。我的一个函 ... -
Struts 2 + Spring 2 + JPA + AJAX示例
2009-09-12 21:18 2540这个例子其实就是来自Struts 2的文档,但是原例子针对的是 ... -
Java线程编程学习笔记(二)
2009-06-11 17:23 1281这里是上一篇:Java线程编程学习笔记(一) Java线程编 ... -
Java线程编程学习笔记(一)
2009-04-09 10:46 2147"Java Thread Programming&q ... -
学习Spring 2.5和Hibernate 3的代码示例
2008-06-06 16:01 2462代码内容(每个包都是一个独立的应用,彼此不干涉): 一个最小 ...
相关推荐
当创建哈希表(HashTable)时,我们通常会使用标准模板库(STL)中的`std::unordered_map`。这是一个简单的C++代码示例,演示如何使用`std::unordered_map`来实现哈希表: #include #include #include int main...
HashMap基于哈希表(HashTable)实现,它通过散列算法将键值对映射到数组中。在HashMap中,每个键值对都有一个唯一的哈希码,该哈希码决定了键值对在数组中的位置。当插入一个键值对时,HashMap会计算键的哈希码,...
HashMap为什么是线程不安全的?如何解决HashMap的线程不安全问题?
基于原子操作的无锁hashtable源码
哈希表(HashTable) 树形数据结构 二叉树(BinaryTree)、二叉搜索树(BinarySearchTree、BST) 平衡二叉搜索树(BalancedBinarySearchTree、BBST) AVL树(AVLTree)、红黑树(RebBlackTree) B树(B-Tree) 集合...
哈希表有时您需要在内存中存储大量数据,以至于V8可能会被阻塞。 这个Node.js模块为V8内存限制之外的本机hashmap数据结构提供了接口。 要安装,只需: npm install hashtable“但是以撒,javascript已经有了哈希表!...
总体介绍 之所以把HashSet和HashMap放在一起讲解,是因为二者在Java里有着相同的实现,前者仅仅是对后者做了一层包装,也是说... 根据对冲突的处理方式不同,哈希表有两种实现方式,一种开放地址方式(Open addre
│ Java面试题04.java中int占几个字节.mp4 │ Java面试题05.java面向对象的特征.mp4 │ Java面试题06.装箱和拆箱.mp4 │ Java面试题07.==和equals的区别.mp4 │ Java面试题08.String.mp4 │ Java面试题09.讲一下java...
HASHMAP基于哈希表的 Map 接口的实现。此实现提供所有可选的映射操作,并允许使用 null 值和 null 键。(除了非同步和允许使用 null 之外,HashMap 类与 Hashtable 大致相同。)下面小编来带大家详细了解下吧
1. Map集合和Collection集合一点关系都... HashMap:线程不安全,底层是哈希表数据结构 Hashtable(用的很少):线程安全,底层也是哈希表结构,所有方法都带有synchronized关键字。 Hashtable有一个子类:Properties
Java中Lambda表达式的使用.docx JAVA多线程之线程间的通信方式.docx Java注解详解.docx Java线程池.docx JDK1.8Stream操作.docx JDK8有新特性.docx JVM堆三代.docx JVM的垃圾回收机制详解和调优.docx Spring源码分析...
是不是觉得很熟悉,没错这玩意在1.8之前的结构就和HashTable一样都是采用数组+链表,同样也是通过链地址法(这里简称拉链法)来解决冲突,但是HashMap和HashTable的区别是一个是线程安全的,一个是非线程安全的。...
为此,我们将使用在文件hashmap.c中找到的以下结构(哈希表) struct Pair { char * key; void * value;};struct HashMap { Pair ** buckets; long size; //cantidad de datos/pairs en la tabla long capac
本文首先针对 Java 集合接口进行了一些介绍,并对这些接口的实现类进行详细描述,包括 LinkedList、...Java 提供了集合框架来解决此类问题,线性表、链表、哈希表等是常用的数据结构,在进行 Java 开发时,JDK 已经为我
通过使用哈希表反转索引哈希函数SSF:简单求和功能PAF:多项式累加函数
Vector,ArrayList, LinkedList的区别是什么? 答: 1. Vector、ArrayList都是以类似数组的形式存储在内存中,LinkedList则以链表的形 式进行存储。 2. List中的元素有序、允许有... HashTable中hash数组的默认大小是1
底层哈希表,基于hashCode的equals的比较方式,线程不安全,存取速度快。 SortedSet 标记: interface TreeSet 标记: class 实现comparable接口,元素是以二叉树的形式存放的。线程不安全 CopyOnWriteArraySet 标记:...
Java哈希表Java Hash Table的实践与实现
【基础】java中String、StringBuffer、StringBuilder的区别 21 【基础】运行时异常和非运行时异常 参见 21 运行时异常 21 非运行时异常 22 【基础】java引用类型 23 强引用(StrongReference) 23 软引用...
为此,我们将使用在文件hashmap.c中找到的以下结构(哈希表) struct Pair { char * key; void * value;};struct HashMap { Pair ** buckets; long size; //cantidad de datos/pairs en la tabla long capac