1. 理解
为每个要被存储的对象给定一个关键字,用一个Hash函数,把这个关键字映射到一个存储单元的地址. 这样, 在查找这个对象的时候, 只需要知道该对象的关键字. 再通过Hash函数, 便可以直接到该地址下的内存单元中去寻找所需要的数据.
但是,这当中又存在一个问题.. 对于每个不同的关键字. 通过Hash函数得到的地址是不是绝对不一样 ? 我是不知道会不会绝对不一样.. 但是数学家们说不同的关键字通过Hash函数也会有可能得到一样内存地址(胡*总说的好, 数学家说什么你就得信什么).
于是又出现一个问题: 解决Hash冲突.
解决Hash冲突的方法:1)拉链法;
2)开放定址法;
3)双Hash函数法;
......
ps:(1) 拉链法: 即不同对象的关键字通过Hash函数得到的内存地址的值如果是一样的的话, 就将这两个(或多个)对象存储在一条线性链表中
如图:{dt1,dt8}, {dt4, dt7}, {dt3, dt6, dt10}, {dt2, dt9}通过Hash函数算得的地址值是一样的, 故它们分别用一条链接起来, 可以看出, 该表中的数组里的每个元素其实是一个链表的表头.
(2) 开放定址法: 就是通过Hash函数算得的地址如果是一样的话, 就往该地址之后的存储空间去寻找, 只要找到有空间可以存储, 就把该数据放到该空间里存储起来 (线性探查法; 平方探查法)
(3) 双Hash函数法: 即给定两个Hash函数, 当通过第一个Hash函数得到的地址与其他数据地址冲突时, 将得到的值通过另外一个Hash函数再得到一个地址值, 用来尽量避免冲突.(可以扩展到多Hash函数)
不难看出, 一个Hash表的存储性能与其Hash函数有着很密切的联系
而Hash函数又有多种构造方法:1) 直接定址法;
2) 除留余数法;
3) 数字分析法
........;
ps: (1) 直接定址法: 就是通过各个要被存储的数据的关键字本身或者加上某个常量值作为地址(个人觉得: 如果一个Hash表通过这样的方法来构造, 我还是直接显式的用数组算了).
(2) 除留余数法: 以各个数据的关键字除以某个不大于Hash表长度的数, 得到的余数作为该数据的Hash地址.
(3) 数字分析法: ... 这个就是得看具体问题了.
2. 实现(1):
首先,是Hash函数. 开始我是采用的取余的方法; 当存储的数据总量达到Map的0.75的时候,就开始扩容,每次扩大为原来的两倍. 话不多说, 上代码:
public class HashTest<K, V> {
// 记录Map的长度
private static int size;
// 存放数据的数组
private Node[] nodeArray;
// 初始容量为11
private static int CAPACITY = 11;
// 数组中存放的数据为数组总长度的0.75则扩容
private static float LOAD_FACTORY = 0.75f;
/**
* @param Capacity
* 指定Map容量
* @param Factory
* 构造因子
*/
HashTest(int Capacity, float Factory) {
if (Capacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: "
+ Capacity);
if (Factory <= 0 || Float.isNaN(Factory))
throw new IllegalArgumentException("Illegal load factor: "
+ Factory);
this.CAPACITY = Capacity;
this.LOAD_FACTORY = Factory;
size = 0;
nodeArray = new Node[CAPACITY]; // 以该容量为长度创建结点数组
}
/**
* 无参构造器
*/
HashTest() {
this(CAPACITY, LOAD_FACTORY);
}
// 以取模得到的值为下标
public void put(K Key, V Value) {
size++;
Node node = new Node<K, V>(Key, Value);
node.hash = Key.hashCode();
int index = Math.abs(node.hash % CAPACITY);
// 如果放在数组中的此位置原来没有元素时, 加在本位置
if (nodeArray[index] == null) {
nodeArray[index] = node;
} else {// 如果原来有元素, 则把本位置的元素替换成新加的元素, 原来在此位置的元素链接到新加元素后
node.next = nodeArray[index];
nodeArray[index] = node;
}
if ((float) size / (float) CAPACITY > LOAD_FACTORY) {
CAPACITY = 2 * CAPACITY;// 更新Map容量
extend(CAPACITY);// 判断是否扩容
}
}
// 根据Key查找映射当中Value值的方法
public V get(K Key) {
int index = Math.abs(Key.hashCode() % CAPACITY);
Node node = null;
V reuslt = null;
for (node = nodeArray[index]; node != null; node = node.next) {
if (Key.equals(node.k)) {
reuslt = (V) node.v;
break;
}
}
return reuslt;
}
// 扩容的方法
public void extend(int Capacity) {
Node[] newArray = new Node[Capacity];
for (int i = 0; i < nodeArray.length; i++) {
if (nodeArray[i] != null) {
Node n = nodeArray[i];
while (n != null) {
Node next = n.next;
int index = Math.abs(n.hash % Capacity);
if (newArray[index] == null) {
newArray[index] = n;
n.next = null;
} else {// index位置下原来就有元素
n.next = newArray[index];
newArray[index] = n; // 将新添加的元素放到该位置,
}
n = next;
}
}
}
nodeArray = newArray;// 更新数组
}
public int size() {
return size;
}
// 用来存放键值对
class Node<K, V> {
K k;
V v;
int hash; // 存储当前放在数组中的结点的hash code
Node<K, V> next;// 同一个hash值下, 此值存储的是下一个Node的地址
Node(K k, V v) {
this.k = k;
this.v = v;
}
}
}
由于Hash函数比较简单, 存储的性能还算过的去, 以下是测试方法:
public static void main(String args[]) {
HashTest map = new HashTest<String, String>();
long time = System.currentTimeMillis();
for (int i = 0; i <= 1000000; i++) {
map.put("" + i, "" + i);
}
long time1 = System.currentTimeMillis();
System.out.println("存储时间:" + (time1 - time));
long time2 = System.currentTimeMillis();
String s = (String) map.get("1000000");
long time3 = System.currentTimeMillis();
System.out.println("查找时间:" + (time3 - time2) + " 查找到的Value值:" + s);
}
存储一百万个数据, 最后输出的结果是:
存储时间:2242
查找时间:0 查找到的Value值:1000000
实现(2):
看了下Java中HashMap的源代码, 对于以下的hash函数和indexFor函数比较有兴致(各种位运算, 觉得没兴致才怪... 好吧, 其实..之所以会想到用系统给的方法, 是因为之前在用取余数法的时候碰到了一些小问题, 导致性能低下的不能再低下, 然后就写了这个实现):
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);
}
static int indexFor(int h, int length) {
return h & (length-1);
}
public class HashTest<K, V> {
private int size; // 元素个数
// 初始容量为11
private static int CAPACITY = 11;
// 数组中存放的数据为数组总长度的0.75则扩容
private static float LOAD_FACTORY = 0.75f;
private Node<K, V>[] nodeArray;// 存储结点的数组
// 指定容量个构造因子的构造函数
@SuppressWarnings("unchecked")
HashTest(int Capacity, float Factory) {
if (Capacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: "
+ Capacity);
if (Factory <= 0 || Float.isNaN(Factory))
throw new IllegalArgumentException("Illegal load factor: "
+ Factory);
CAPACITY = Capacity;
LOAD_FACTORY = Factory;
size = 0;
nodeArray = new Node[CAPACITY];
}
// 无参构造函数
HashTest() {
this(CAPACITY, LOAD_FACTORY);
}
// 得到hash码 (借用系统的方法)
private int hash(int h) {
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
// 根据hash code来得到元素要放在哪个位置(借用系统的方法)
private int FindIndex(int hash, int length) {
return hash & (length - 1);
}
// 存放键值对
@SuppressWarnings("unchecked")
public void put(K Key, V Value) {
size++;
Node node = new Node();
node.k = Key;
node.v = Value;
// 得到本结点的hash码. 放入结点中, 用于之后扩容.
int hash = hash(Key.hashCode());
node.hashcode = hash;
int index = FindIndex(hash, CAPACITY); // 找到要放的位置
node.next = nodeArray[index]; // 原来在该位置的元素链到要添加的本元素后
nodeArray[index] = node; // 将新添加的元素放到该位置
if ((float) size / (float) CAPACITY > LOAD_FACTORY) {// 总个数大于数组容量的0.75时就扩容
CAPACITY *= 2;
extend(CAPACITY);
}
}
// 扩容的方法
@SuppressWarnings("unchecked")
private void extend(int capacity) {
Node[] newArray = new Node[capacity];
Node n = null, next = null;
for (int i = 0; i < nodeArray.length; i++) {
if ((n = nodeArray[i]) != null) { // 该位置上有元素的时候
while (n != null) {// 重新放置每个元素的位置
next = n.next;
int index = FindIndex(n.hashcode, capacity);
n.next = newArray[index]; // 将本来在该位置上的元素放到将被放到此位置上的元素之后
newArray[index] = n;
n = next;
}
}
}
nodeArray = newArray;
}
// 根据Key值得到Map中的元素值
@SuppressWarnings("unchecked")
public V get(K Key) {
int hash = hash(Key.hashCode());
int index = FindIndex(hash, CAPACITY);
Node node = null;
V reuslt = null;
for (node = nodeArray[index]; node != null; node = node.next) {
if (Key.equals(node.k)) {
reuslt = (V) node.v;
break;
}
}
return reuslt;
}
}
// 结点类
class Node<K, V> {
int hashcode; // 存储自己的hash码, 便于之后的查找
K k;
V v;
Node<K, V> next; // 下一个结点地址
}
最后的存储性能确是比取余法要差了那么一点: 同样是一百万个数据存储, 这次用了 2600 多毫秒.
以下是测试方法:
public static void main(String args[]) {
HashTest<String, String> map = new HashTest<String, String>();
long time = System.currentTimeMillis();
for (int i = 0; i <= 1000000; i++) {
map.put("" + i, "" + i);
}
long time1 = System.currentTimeMillis();
System.out.println("存储时间:" + (time1 - time));
long time2 = System.currentTimeMillis();
String s = (String) map.get("1000000");
long time3 = System.currentTimeMillis();
System.out.println("查找时间:" + (time3 - time2) + " 查找到的Value值:" + s);
}
这次的存储一百万个数据输出的结果:
存储时间:2632
查找时间:0 查找到的Value值:1000000
- 大小: 18.2 KB
分享到:
相关推荐
下面将详细介绍Hash表的概念、哈希函数的选择、冲突解决策略以及C语言实现Hash表的基本步骤。 1. **哈希表概念** 哈希表是一种基于键值对的数据结构,它的核心在于哈希函数,它将键转化为数组的索引。理想情况下,...
在IT领域,理解和掌握哈希表的实现方式至关重要,因为它广泛应用于数据库系统、编程语言解释器以及各种需要高效数据检索的场景。 本文将详细探讨三种常见的哈希表实现方法:链地址法、线性探测法和双重散列表。 1....
STM32F407是意法半导体(STMicroelectronics)推出的一款基于ARM Cortex-M4内核的微控制器,广泛应用于各种嵌入式系统中。...通过分析`HASH`文件,开发者可以深入理解如何在微控制器上实现高效、安全的哈希计算。
在压缩包文件"C-hash"中,很可能包含了实现上述功能的C语言源代码,包括哈希表结构定义、哈希函数、冲突解决机制以及插入、查找和删除操作的函数。通过阅读和理解这些代码,你可以深入学习到C语言实现哈希表的具体...
在编程领域,哈希表(Hash Table)是一种高效的数据结构,它通过特定的哈希函数将数据映射到一个固定大小的数组中,以实现快速的查找、插入和删除操作。哈希表的关键在于设计良好的哈希函数,该函数能够尽可能均匀地...
根据提供的文件信息,我们可以深入分析C语言中哈希表(Hash Table)的实现方式与具体细节。本篇文章将从以下几个方面展开讨论: 1. **哈希表的基本概念** ...这对于理解哈希表的基本原理及其实现细节非常有帮助。
在本话题中,我们将深入探讨哈希表法如何实现散列以及再散列,同时以C++为编程语言进行实例解析。 首先,理解哈希函数是关键。哈希函数的目标是将任意大小的输入(如电话号码)转化为固定大小的输出(通常是数组的...
**正文** `GEOHASH` 是一种地理位置编码技术,它将经纬度坐标转换为字符串,以...通过这些文件,开发者可以学习并理解`GEOHASH`在JavaScript环境中的具体实现,以及如何与地图API结合,实现高效的地理位置索引和查询。
标题中的“hash.rar_HASH算法_fpga hash_hash_zebra85v_哈希表Verilog”揭示了这个压缩包文件的主要内容,它涉及到哈希(Hash)算法在高速Field-Programmable Gate Array(FPGA)上的实现,以及与Zebra85v硬件平台和...
在"hash表模板类"这个压缩包中,你可能找到了一个实现了以上功能的C++源文件。通过阅读和理解代码,你可以学习到自定义哈希表的实现细节。此外,附带的测试代码和可运行文件可以帮助你验证该哈希表模板类的正确性,...
为了更好地理解并实现GeoHash算法,你可以参考`geoHash`压缩包中的源代码,它可能包含了实现GeoHash功能的类和方法。通过阅读和学习这些代码,你可以深入理解GeoHash的工作原理,并将其应用于自己的项目中。同时,...
双向链表和哈希表在实际编程中都有着广泛的应用,理解它们的工作原理和使用方式对于提升程序性能和可维护性至关重要。通过学习和实践,开发者可以灵活运用这些数据结构来解决各种复杂问题。在具体实现中,需要考虑...
在本项目中,“avl树实现hash表”可能是为了利用avl树的特性来优化哈希表的冲突处理。一种可能的实现方式是,每个桶不再是一个简单的链表,而是一个avl树。这样,当冲突发生时,所有映射到同一桶的键会被存储在avl树...
通过阅读源代码,我们可以深入了解Delphi中哈希表的具体实现细节,包括所选的哈希函数、冲突解决策略以及如何高效地管理内存和操作元素。这不仅有助于理解哈希表的工作原理,还可以为我们自己的编程项目提供灵感和...
总结文档`hash表.doc`和`hash总结.doc`可能涵盖了哈希表的基本概念、原理、哈希函数的设计、冲突解决策略以及哈希表在实际应用中的案例分析。深入阅读这些文档将有助于进一步理解哈希表的工作机制及其在软件开发中的...
本项目是用C语言实现的哈希算法,包括SHA256、SHA384和SHA512三种不同的哈希函数,这些函数是SHA-2(Secure Hash Algorithm 2)家族的一部分。 SHA-2是由美国国家安全局(NSA)设计的,包含了多种不同长度的哈希...
哈希(Hash)算法在计算机科学中扮演着重要的角色,特别...同时,为了处理碰撞,可以结合链地址法、开放寻址法或者双重哈希等方法实现哈希表。在压缩包中的`hash`文件可能包含了更多不同哈希函数的实现,供学习和参考。
`hash.c`通常包含了哈希表的函数实现,而`hash.h`则包含对外的头文件,定义了哈希表的数据结构和相关的接口函数。 在`hash.h`中,可能会定义如下的数据结构: ```c typedef struct HashNode { void* key; void* ...
`study-hash`这个文件可能是对哈希表学习的代码实现,包括了哈希函数的设计、冲突处理方法的实现,以及可能的一些性能测试。通过阅读和理解这个程序,你可以更深入地掌握哈希表的工作原理和实际运用。在实践中,不断...
在C语言中实现哈希表,我们需要理解哈希函数的设计、冲突解决策略以及动态扩容等核心概念。 哈希函数是哈希表的核心,它的主要任务是将输入的关键字(key)转化为数组的下标。一个理想的哈希函数应具备以下特性:...