`

对hash思想的理解以及hash表的实现

阅读更多
新的问题总是导致了新的理论和新技术的诞生,其中在计算机领域的有一件事情却不得不提出来让我们讨论一下,那边是java编程语言中的一种数据结构hash集合。java中hash集合最常用的有三种,分别是:hashSet,hashMap及其hashTable。
---中国大姨夫



一:哈希算法诞生的背景


   在十九世纪后半叶,计算机技术飞速发展,为了适应不断提高的高指标运行环境,计算机语言也是层出不穷,其中著名的有c/c++、java、jScript以及后来的c#等等。这些高级计算机语言成为了广大程序员手中的强有力的开发利器。然而在最早的时候,并没有出现像今天如此方便的计算机语言给我们自由发挥,但是随着信息时代的步步紧逼,新的问题就产生了。

       由于信息量过大,使用传统的数据存储方法显然已经满足不了人们需求。因为那时在计算机中数据的存储结构的根本方法只有两种:数组和链表。这两种存储方法各有各自的优点和劣势。例如数组的优势在于数组的长度是固定的,它的每一个下标都指向着唯一的一个值,所以我们知道这样一来的话要在数组中找到一个元素就非常方便了,只需要知道该元素在数组的索引就行了。但是长度固定同时又成了他的缺点,当我们用一个数组来存储一些数据时,需要指定他的长度,但是我们又不知道我们的数据是否就可以被该数组全部装下,一旦超出了数组的长度就会出错。同时如果我们定义一个长度足够长的数组的话又没有必要,因为这样会占用很大一部分的内存,造成计算机的资源浪费。而且当我们要删除不必要的元素时,该索引位置的内存空间是不能被释放的。链表的优势的就在于存储数据时我们只需要将数据不断地接在节点上就行了,这也就意味着链表的长度的没有限制的,所以我们可以很方便的对链表中的数据进行插入,删除等操作。但是由于链表的每一个数据都是环环相扣的,所以当我们需要查询某一个元素时就不得不遍历所有的节点。这时效率就大打折扣了。

      所以我们是否能够找到一个综合了数组和链表各自的优点的一种数据存储方式呢?答案就是哈希算法。哈希算法是由hash这个人发明的,哈希算法将任意长度的二进制值映射为固定长度的较小二进制值,这个小的二进制值称为哈希值。哈希值是一段数据唯一且极其紧凑的数值表示形式。如果散列一段明文而且哪怕只更改该段落的一个字母,随后的哈希都将产生不同的值。要找到散列为同一个值的两个不同的输入,在计算上是不可能的,所以数据的哈希值可以检验数据的完整性。

  哈希表是根据设定的哈希函数H(key)和处理冲突方法将一组关键字映象到一个有限的地址区间上,并以关键字在地址区间中的象作为记录在表中的存储位置,这种表称为哈希表或散列,所得存储位置称为哈希地址或散列地址。作为线性数据结构与表格和队列等相比,哈希表无疑是查找速度比较快的一种。

   关于equals()方法和hashCode()方法的区别和联系大家可以花多点时间去关注一下。

         二:哈希算法中的关键点

  [size=x-small;] 说到hash[/size]算法的成功实现其实关键归功于hashCode的应用。当然这是我个人的理解。[size=medium;]初学者可以这样理解,hashCode[/size]方法实际上返回的就是对象存储的物理地址(实际可能并不是)。    这样一来,当集合要添加新的元素时,先调用这个元素的hashCode方法,就一下子能定位到它应该放置的物理位置上。如果这个位置上没有元素,它就可以直接存储在这个位置上,不用再进行任何比较了;如果这个位置上已经有元素了,就调用它的equals方法与新元素进行比较,相同的话就不存了,不相同就散列其它的地址。所以这里存在一个冲突解决的问题。这样一来实际调用equals方法的次数就大大降低了,几乎只需要一两次

[size=medium;] [/size]

        三:实现hash表的基本思路

    由于hash表其实是一个数组+链表的结合体,所以要实现它必须结合数组和链表的知识构建。下面是本人对构建hash表的基本思路。

    1.我们需要指定一个具有初始容量的数组,这个数组的每一个元素实际上是一个链表。例如我们可以这样构建:

  

[code="java"]private int max=0 ;//实际存储数据的最大容量  max = init_capacity*load_factor;
private Entry[] entry;//用来存储数据的数组  此时相当于一张hash表
/**
* 构造函数  这里由于只以测试为目的就直接使用默认的构造器了
*/
public MapMain(){
max = (int) (init_capacity*load_factor);//将最大容量确定下来
entry = new Entry[init_capacity];//实例化这个数组容器
}
 

   在构造函数中就创建数组,并且指定最大数据容量。

2.我们还需要一个节点类,因为我们是自己做一张hash表,所以我们可以将该类封装成一个内部类:


[code="java"]/**
* 定义一个泛型类
* 创建一个内部类   这里不直接实现系统的Map.Entry接口
*/
class Entry {
//将当前节点的父节点和子节点封装起来
Entry lastCode;
Entry nextCode; 
K key; 
V value;  
int hash;
// 构造方法  
Entry(K k, V v, int hash) {  
this.key = k;  
this.value = v;  
this.hash = hash;  

}  
}


   其中K,V就是我们最熟悉的键值对,所以用过hashMap的人们都知道。


       3.接下来就是最关键的步骤了,即map中添加元素的方法。该方法决定了数据在map表中的存储方法。

其实思路也很简单,我们可以用用一张图表很直观的看到:

[img]http://dl.iteye.com/upload/attachment/0065/9574/a1b700dc-588a-3df1-8ed0-8893dc189f30.jpg" alt="[/img]



其中的双向箭头表示里面的每一个链表都是双向链表,这样的话可以方便后面的操作。


4.重建hashMap。这一步是很重要的一步,它是hash表的一个显著特点,因为关乎hash表的效率问题。这里首先要有一个控制量,这个控制量就是hashMap的加载因子。jdk类库里面使用的0.75f,当然这个可以随自己的需要而定。当这个hash表中的数据量超过了我们所设定的限度的时候,比如说我们设定为maxSize  = init_Capacity*0.75f,当size>maxSize时我们就reSetHash。


四: 下面是我自己的一个hashMap的实现代码

  

[code="java"]package 哈希Map;
/**
* 基本思路是用一个泛型类作为节点  然后将该节点作为一个数组的元素
* 所有的数据将存储在这个数组中    即通常所说的挂链式存储方法
* @author nanxia
* @param
* @param
*/

public class MapMain {
public static int init_capacity = 32 ;//初始容量
public static float load_factor = 0.75f;//加载因子
private int size=0;//集合中的容量
private int max=0 ;//实际存储数据的最大容量  max = init_capacity*load_factor;
private Entry[] entry;//用来存储数据的数组  此时相当于一张hash表
/**
* 构造函数  这里由于只以测试为目的就直接使用默认的构造器了
*/
public MapMain(){
max = (int) (init_capacity*load_factor);//将最大容量确定下来
entry = new Entry[init_capacity];//实例化这个数组容器
}
/**
* 定义hash函数   使用简单&位运算符
* 当然我们还可以尝试其他的方法  比如取余%运算等
*/
public int hashFuction(int hashCode,Entry[] entry){
int i = hashCode&(entry.length-1);
return i;
}
/**
* put方法   添加元素进去
*/
public boolean put(K key, V value){
int hash = key.hashCode();//获取键的哈希码
Entry entryCode = new Entry(key,value,hash);//创建数组的一个节点
//先判断是否需要重建
if(size>=max){
reSet(entry.length*5);
}
//添加元素  并且使数据量加一
if(add(entryCode,entry)){
size++;
return true;
}
return false;

}
/**
* 在封装一个方法去添加元素
*/
public boolean add(Entry code,Entry[] entry){

int hash = code.hash;//获取键的哈希码
int index = hashFuction(hash,entry);//通过哈希函数获取到数组的索引位置
//System.out.println("哈希码:"+hash+"索引位置:"+index);
if(entry[index]==null){
entry[index]=code;//如果该索引位置上没有元素
}else{
Entry next = entry[index].nextCode;
while(next!=null){
//如果添加的元素是重复的
if(next.hash==hash&&next.key.equals(code.key)) return false;
next = next.nextCode;
}
//将链表头储存起来
Entry headCode =entry[index];
//执行到这一步可以知道没有重复的元素  将要添加的元素添加到数组索引位置 即链表头位置
entry[index]=code;
//将链表连接上来
code.nextCode=headCode;
headCode.lastCode=code;
}
return true;

}
/**
* 定义reSet方法   即当容量超过上限时   重建hashMap
*/
public void reSet(int reSize){
//System.out.println("hello");
max = (int) (reSize*load_factor);
Entry[] newEntry = new Entry[reSize];//创建一个容量大于初始容量的新数组
//只需要通过for循环和while循环将每一个数据取出再重新加入到新数组就行
for(int i=0;i headCode = entry[i];
if(headCode!=null){
//********千万要注意这里从原数组中取出的节点不能直接调用add()方法
//因为原数组中的节点包含了对父、子节点的索引   所以直接加的话会出现死循环的错误
//所以必须创建新节点再调用add()方法添加
//这个花了本人很多时间去调试的
//根据原数组中的k、V、hash创建新节点  对父、子节点的引用就不用了
Entry newCode = new Entry(headCode.key,headCode.value,headCode.hash);
add(newCode,newEntry);
Entry next = headCode.nextCode;
while(next!=null){
//同样创建新节点
Entry newNext = new Entry(next.key,next.value,next.hash);
System.out.println(next.key+"死循环!!!");
add(newNext,newEntry);
next = next.nextCode;

}
}else continue;

}
entry = newEntry;//有数组指向新数组
}
/**
* 定义get方法  从map中去的元素
*/
public V getValue(K key){
int hash = key.hashCode();
int index = hashFuction(hash,entry);//获取要搜索的索引
if(entry[index].key.equals(key)){
return entry[index].value;
}else{
Entry next = entry[index].nextCode;
while(next!=null){
if(next.key.equals(key)) return next.value;//遍历该条子链表
next = next.nextCode;
}
}
return null;
}
/**
* remove方法  从map中移除一个元素
*/
public boolean remove(K key){
int hash = key.hashCode();
int index = hashFuction(hash,entry);//获取要搜索的索引
//如果哈希码一样的话则进入下一部   否则hash集合中就没有要找的元素
if(entry[index].key.equals(key)){
entry[index]=null;//如果要删除的元素是链表头
return true;
}else{
Entry next = entry[index].nextCode;//获得下一个节点
while(next!=null){//遍历该条子链表
if(next.key.equals(key)){
Entry next2 = next.nextCode;
//如果next不是最后一个节点
if(next2!=null){
//那么被删除的节点的父节点的子节点应该指向其子节点
next.lastCode.nextCode=next2;
return true;
}else{//如果next是最后一个节点
next.lastCode.nextCode=null;
}
}
next = next.nextCode;
}
}
return false;

}
/**
* 定义一个泛型类
* 创建一个内部类   这里不直接实现系统的Map.Entry接口
*/
class Entry {
//将当前节点的父节点和子节点封装起来
Entry lastCode;
Entry nextCode; 
K key; 
V value;  
int hash;
// 构造方法  
Entry(K k, V v, int hash) {  
this.key = k;  
this.value = v;  
this.hash = hash;  

}  
}
}


   这是我自己根据hash表的原理做的一个map,该表仅实现了put、get、remove等基本方法。仅供参考!


   下面是对上述map的一个测试类


[code="java"]package 哈希Map;

import java.util.HashMap;

public class TestMap {
/**
* 主类
* @param args
*/
public static void main(String[] args) {
//*****自己写的map
MapMain map = new MapMain();
int start = (int) System.currentTimeMillis();
for(int i=0;i hash = new HashMap();
int start2 = (int) System.currentTimeMillis();
for(int i=0;i这个接口可能有优越的性能,我的代码中没有直接实现这个接口。

  • 大小: 65.8 KB
分享到:
评论

相关推荐

    GEOHASH Javascript的实现

    **正文** `GEOHASH` 是一种地理位置编码技术,它将经纬度坐标转换为字符串,以...通过这些文件,开发者可以学习并理解`GEOHASH`在JavaScript环境中的具体实现,以及如何与地图API结合,实现高效的地理位置索引和查询。

    hash表C语言实现

    在压缩包文件"C-hash"中,很可能包含了实现上述功能的C语言源代码,包括哈希表结构定义、哈希函数、冲突解决机制以及插入、查找和删除操作的函数。通过阅读和理解这些代码,你可以深入学习到C语言实现哈希表的具体...

    geohash算法实现Java代码

    GeoHash算法的核心思想是利用二进制编码将地球表面的空间进行细分。首先,我们将地球视为一个二维的平面,然后采用经纬度坐标系统。地球的经度范围是-180到180度,纬度范围是-90到90度。GeoHash算法会将这个范围不断...

    图像的相似度Hash算法(aHash的delphi实现).rar

    在Delphi中实现aHash,需要理解算法的基本流程,并能够利用Delphi的图像处理和二进制操作功能。通过这个压缩包,你可以学习到如何在Delphi环境下编写图像Hash算法,从而提升你在图像处理领域的技能。

    如何找到周围8个区域的GeoHash编码

    以上就是关于“如何找到周围8个区域的GeoHash编码”的详细说明,包括GeoHash的基本原理、Java实现以及在实际应用中的用法。通过理解这些概念,你可以在Java项目中有效地处理和查询地理位置数据。

    几种经典的Hash算法的实现(源代码)

    ### 经典Hash算法概述与实现 #### 一、引言 哈希算法在计算机科学领域扮演着极其重要的角色,特别是在数据检索、信息安全以及数据完整性校验等方面。它能够将任意长度的数据转换成一个固定长度的哈希值,这一过程在...

    一致性Hash算法的原理及实现

    ### 一致性Hash算法的原理及实现 #### 一、引言 一致性Hash算法是一种用于解决分布式环境下数据存储和检索问题的重要技术。它最初由David Karger等人在1997年的论文《Consistent Hashing and Random Trees: ...

    encode_geohash.rar_geohash_geohash encode_matlab与geohash

    在给定的“encode_geohash.rar”压缩包中,包含了一个名为“encode_geohash.m”的MATLAB程序,这是对GeoHash编码的一种实现。MATLAB作为一种强大的数学计算环境,常用于各种科学计算和数据分析,包括地理信息系统...

    二分查找和hash表的实现

    而哈希表则广泛应用于缓存、数据库索引、字典实现、集合和映射等数据结构。在软件开发中,了解和熟练掌握这两种技术能极大提高代码的执行效率。 综上所述,二分查找和哈希表是编程领域中的重要工具,它们各自在不同...

    hash_basic.rar_hash表_哈希搜索_哈希表 基本操作

    在"hash_basic.rar"这个压缩包中,可能包含了一些关于哈希表基础操作的代码示例或教学资料,用于帮助理解并实现这些操作。 1. **哈希函数**: 哈希函数是哈希表的关键,它的作用是将任意长度的输入(通常是字符串...

    test-hash.zip_UTHASH_hashtest

    这个压缩包"test-hash.zip_UTHASH_hashtest"包含了UTHASH的最新源码以及使用示例,这对于理解和在你的项目中集成UTHASH非常有帮助。 UTHASH 提供了一种简洁的方式来为结构体对象添加哈希表功能,允许你通过指定的键...

    c语言的hash-lru实现

    在IT行业中,C语言是一种基础且强大的编程语言,尤其在系统级编程和底层开发中...通过理解和实现这个项目,开发者可以深入理解哈希表、链表以及LRU缓存策略的工作原理,这对于提升系统设计和数据结构能力非常有帮助。

    开源项目-cznic-hash.zip

    【cznic-hash开源项目概述】 cznic-hash是一个开源项目,主要设计...总之,cznic-hash项目为处理非可比较键提供了新的可能性,无论你是想学习哈希表的实现,还是寻找一种适用于特殊场景的映射工具,它都值得深入研究。

    哈希表Hash table 用于哈希表等的 C 宏

    哈希表是一种在计算机科学中广泛使用的数据结构,它的核心思想是通过特定的函数(哈希函数)将任意长度的键映射到一个固定大小的数组索引上,从而实现快速查找、插入和删除操作。在C语言中,由于其低级特性,通常...

    BFS+hash.rar_bfs_hash ACM_hash acm

    **哈希表**是一种数据结构,它通过哈希函数将键(Key)映射到一个固定大小的数组中,以实现快速查找、插入和删除操作。哈希表的时间复杂度在理想情况下可以达到O(1),大大提高了效率。在ACM竞赛中,哈希表常用于存储...

    nginx负载均衡中RR和ip_hash策略分析

    - 实现简单,易于理解。 - 每次请求按顺序依次分配给不同的服务器,使得每台服务器处理的请求量大致相同。 - 当某台服务器宕机时,可以自动跳过该服务器,避免了无效的请求。 - **适用场景**: - 当所有服务器...

    hash二分查找实验8.rar

    他可能通过编程实现了哈希表和二分查找算法,并对其性能进行了分析和比较,以理解它们在不同场景下的适用性。 在实际应用中,哈希查找常用于数据库索引、缓存系统等需要快速查找的场景,而二分查找则常见于搜索引擎...

    hash_lookup3

    《哈希函数:深入理解hash_lookup3》 在信息技术领域,哈希函数是数据结构与算法中的重要组成部分,它能够将任意长度的数据映射到固定长度的哈希值,广泛应用于数据库索引、缓存(如memcached)以及加密等领域。...

    链式哈希表hash

    哈希表(Hash Table)的核心思想是通过哈希函数将数据的关键字(key)映射到一个固定大小的数组中,使得查找、插入和删除操作的时间复杂度可以接近O(1)。 哈希函数是链式哈希表中的关键部分,它的主要任务是将...

    geohash-cpp:GeoHash 库

    GeoHash 是一种将地理位置数据(经纬度)编码为字符串的技术,这种编码方法可以方便地进行空间索引和距离估算。...通过深入理解 GeoHash 的原理和实现,可以提升你在地理信息系统(GIS)领域的开发能力。

Global site tag (gtag.js) - Google Analytics