`

Hash表原理及Java实现

    博客分类:
  • Java
阅读更多

 这篇博客主要探讨Hash表中的一些原理/概念,及根据这些原理/概念,自己设计一个用来存放/查找数据的Hash表,并且与JDK中的HashMap类进行比较。

我们分一下七个步骤来进行。 

一。    Hash表概念

 

二 .      Hash构造函数的方法,及适用范围

 

三.       Hash处理冲突方法,各自特征

 

四.       Hash查找过程

 

五.       实现一个使用Hash存数据的场景-------Hash查找算法,插入算法

 

六.       JDKHashMap的实现

 

七.       Hash表与HashMap的对比,性能分析

 

 一。    Hash表概念 

               在查找表中我们已经说过,在Hash表中,记录在表中的位置和其关键字之间存在着一种确定的关系。这样       我们就能预先知道所查关键字在表中的位置,从而直接通过下标找到记录。使ASL趋近与0.

 

              1)   哈希(Hash)函数是一个映象,即: 将关键字的集合映射到某个地址集合上,它的设置很灵活,只要这个地       址集合的大小不超出允许范围即可;

             2)  由于哈希函数是一个压缩映象,因此,在一般情况下,很容易产生“冲突”现象,即: key1¹ key2,而  f            (key1) = f(key2)

              3).  只能尽量减少冲突而不能完全避免冲突,这是因为通常关键字集合比较大,其元素包括所有可能的关键字,       而地址集合的元素仅为哈希表中的地址值

 

       在构造这种特殊的“查找表” 时,除了需要选择一个“好”(尽可能少产生冲突)的哈希函数之外;还需要找到一      种“处理冲突” 的方法。

 

二 .     Hash构造函数的方法,及适用范围

  • 直接定址法
  • 数字分析法
  • 平方取中法
  • 折叠法
  • 除留余数法
  • 随机数法      

 

      1)直接定址法:

                哈希函数为关键字的线性函数,H(key) = key 或者 H(key) = a ´ key + b

              此法仅适合于地址集合的大小 = = 关键字集合的大小,其中ab为常数。

     (2)数字分析法:

             假设关键字集合中的每个关键字都是由 s 位数字组成 (u1, u2, …, us),分析关键字集中的全体,                  并从中提取分布均匀的若干位或它们的组合作为地址。

             此法适于:能预先估计出全体关键字的每一位上各种数字出现的频度。

     (3)平方取中法:

               以关键字的平方值的中间几位作为存储地址。求“关键字的平方值” 的目的是“扩大差别” ,同                    时平方值的中间各位又能受到整个关键字中各位的影响。

             此法适于:关键字中的每一位都有某些数字重复出现频度很高的现象。

     (4)折叠法:

            将关键字分割成若干部分,然后取它们的叠加和为哈希地址。两种叠加处理的方法:移位叠加:将分               割后的几部分低位对齐相加;间界叠加:从一端沿分割界来回折叠,然后对齐相加。

            此法适于:关键字的数字位数特别多。

     (5)除留余数法:

             设定哈希函数为:H(key) = key MOD p   ( p≤m ),其中, m为表长,p 为不大于 m 的素数,                 是不含 20 以下的质因子

     (6)随机数法:

           设定哈希函数为:H(key) = Random(key)其中,Random 为伪随机函数

           此法适于:对长度不等的关键字构造哈希函数。

 

         实际造表时,采用何种构造哈希函数的方法取决于建表的关键字集合的情况(包括关键字的范围和形态),以及哈希表    长度(哈希地址范围),总的原则是使产生冲突的可能性降到尽可能地小。

三.       Hash处理冲突方法,各自特征

 处理冲突” 的实际含义是:为产生冲突的关键字寻找下一个哈希地址。

  •   开放定址法
  •   再哈希法
  •   链地址法

 

      (1)开放定址法:

               为产生冲突的关键字地址 H(key) 求得一个地址序列: H0, H1, H2, …, Hs  1≤s≤m-1,Hi = ( H(key)                 +di  ) MOD m,其中: i=1, 2, …, s,H(key)为哈希函数;m为哈希表长;

 

      (2)链地址法:

             将所有哈希地址相同的记录都链接在同一链表中。

 

      (3)再哈希法:

               方法:构造若干个哈希函数,当发生冲突时,根据另一个哈希函数计算下一个哈希地址,直到冲突不再发                  生。即:Hi=Rhi(key)     i=1,2,……k,其中:Rhi——不同的哈希函数,特点:计算时间增加

 四.       Hash查找过程

 

        对于给定值 K,计算哈希地址 i = H(K), r[i] = NULL  则查找不成功, r[i].key = K  则查找成功, 否则 求     下一地址 Hi” 直至r[Hi] = NULL  (查找不成功)  r[Hi].key = K  (查找成功) 为止。

 

 五.       实现一个使用Hash存数据的场景-------Hash查找算法,插入算法

         假设我们要设计的是一个用来保存中南大学所有在校学生个人信息的数据表。因为在校学生数量也不是特别巨大(8W?),每个学生的学号是唯一的,因此,我们可以简单的应用直接定址法,声明一个10W大小的数组,每个学生的学号作为主键。然后每次要添加或者查找学生,只需要根据需要去操作即可。

      但是,显然这样做是很脑残的。这样做系统的可拓展性和复用性就非常差了,比如有一天人数超过10W了?如果是用来保存别的数据呢?或者我只需要保存20条记录呢?声明大小为10W的数组显然是太浪费了的。

 

     如果我们是用来保存大数据量(比如银行的用户数,4大的用户数都应该有3-5亿了吧?),这时候我们计算出来的HashCode就很可能会有冲突了, 我们的系统应该有“处理冲突”的能力,此处我们通过挂链法“处理冲突”

 

     如果我们的数据量非常巨大,并且还持续在增加,如果我们仅仅只是通过挂链法来处理冲突,可能我们的链上挂了上万个数据后,这个时候再通过静态搜索来查找链表,显然性能也是非常低的。所以我们的系统应该还能实现自动扩容,当容量达到某比例后,即自动扩容,使装载因子保存在一个固定的水平上

 

综上所述,我们对这个Hash容器的基本要求应该有如下几点:

             满足Hash表的查找要求(废话)

 

             能支持从小数据量到大数据量的自动转变(自动扩容)

 

             使用挂链法解决冲突

 

 

好了,既然都分析到这一步了,咱就闲话少叙,直接开始上代码吧。

 

Java代码   收藏代码
  1. package cn.javamzd.collection.search;  
  2.   
  3. public class MyMap<K, V> {  
  4.     private int size;// 当前容量  
  5.     private static int INIT_CAPACITY = 16;// 默认容量  
  6.     private Entry<K, V>[] container;// 实际存储数据的数组对象  
  7.     private static float LOAD_FACTOR = 0.75f;// 装载因子  
  8.     private int max;// 能存的最大的数=capacity*factor  
  9.   
  10.     // 自己设置容量和装载因子的构造器  
  11.     public MyMap(int init_Capaticy, float load_factor) {  
  12.         if (init_Capaticy < 0)  
  13.             throw new IllegalArgumentException("Illegal initial capacity: "  
  14.                     + init_Capaticy);  
  15.         if (load_factor <= 0 || Float.isNaN(load_factor))  
  16.             throw new IllegalArgumentException("Illegal load factor: "  
  17.                     + load_factor);  
  18.         this.LOAD_FACTOR = load_factor;  
  19.         max = (int) (init_Capaticy * load_factor);  
  20.         container = new Entry[init_Capaticy];  
  21.     }  
  22.   
  23.     // 使用默认参数的构造器  
  24.     public MyMap() {  
  25.         this(INIT_CAPACITY, LOAD_FACTOR);  
  26.     }  
  27.   
  28.     /** 
  29.      * 存 
  30.      *  
  31.      * @param k 
  32.      * @param v 
  33.      * @return 
  34.      */  
  35.     public boolean put(K k, V v) {  
  36.         // 1.计算K的hash值  
  37.         // 因为自己很难写出对不同的类型都适用的Hash算法,故调用JDK给出的hashCode()方法来计算hash值  
  38.         int hash = k.hashCode();  
  39.         //将所有信息封装为一个Entry  
  40.         Entry<K,V> temp=new Entry(k,v,hash);  
  41.             if(setEntry(temp, container)){  
  42.                 // 大小加一  
  43.                 size++;  
  44.                 return true;  
  45.             }  
  46.             return false;  
  47.     }  
  48.   
  49.   
  50.     /** 
  51.      * 扩容的方法 
  52.      *  
  53.      * @param newSize 
  54.      *            新的容器大小 
  55.      */  
  56.     private void reSize(int newSize) {  
  57.         // 1.声明新数组  
  58.         Entry<K, V>[] newTable = new Entry[newSize];  
  59.         max = (int) (newSize * LOAD_FACTOR);  
  60.         // 2.复制已有元素,即遍历所有元素,每个元素再存一遍  
  61.         for (int j = 0; j < container.length; j++) {  
  62.             Entry<K, V> entry = container[j];  
  63.             //因为每个数组元素其实为链表,所以…………  
  64.             while (null != entry) {  
  65.                 setEntry(entry, newTable);  
  66.                 entry = entry.next;  
  67.             }  
  68.         }  
  69.         // 3.改变指向  
  70.         container = newTable;  
  71.           
  72.     }  
  73.       
  74.     /** 
  75.      *将指定的结点temp添加到指定的hash表table当中 
  76.      * 添加时判断该结点是否已经存在 
  77.      * 如果已经存在,返回false 
  78.      * 添加成功返回true 
  79.      * @param temp 
  80.      * @param table 
  81.      * @return 
  82.      */  
  83.     private boolean setEntry(Entry<K,V> temp,Entry[] table){  
  84.         // 根据hash值找到下标  
  85.         int index = indexFor(temp.hash, table.length);  
  86.         //根据下标找到对应元素  
  87.         Entry<K, V> entry = table[index];  
  88.         // 3.若存在  
  89.         if (null != entry) {  
  90.             // 3.1遍历整个链表,判断是否相等  
  91.             while (null != entry) {  
  92.                 //判断相等的条件时应该注意,除了比较地址相同外,引用传递的相等用equals()方法比较  
  93.                 //相等则不存,返回false  
  94.                 if ((temp.key == entry.key||temp.key.equals(entry.key)) && temp.hash == entry.hash&&(temp.value==entry.value||temp.value.equals(entry.value))) {  
  95.                     return false;  
  96.                 }  
  97.                 //不相等则比较下一个元素  
  98.                 else if (temp.key != entry.key && temp.value != entry.value) {  
  99.                         //到达队尾,中断循环  
  100.                         if(null==entry.next){  
  101.                             break;  
  102.                         }  
  103.                         // 没有到达队尾,继续遍历下一个元素  
  104.                         entry = entry.next;  
  105.                 }  
  106.             }  
  107.             // 3.2当遍历到了队尾,如果都没有相同的元素,则将该元素挂在队尾  
  108.             addEntry2Last(entry,temp);  
  109.                   
  110.         }  
  111.         // 4.若不存在,直接设置初始化元素  
  112.         setFirstEntry(temp,index,table);  
  113.         return true;  
  114.     }  
  115.       
  116.     private void addEntry2Last(Entry<K, V> entry, Entry<K, V> temp) {  
  117.         if (size > max) {  
  118.             reSize(container.length * 4);  
  119.         }  
  120.         entry.next=temp;  
  121.           
  122.     }  
  123.   
  124.     /** 
  125.      * 将指定结点temp,添加到指定的hash表table的指定下标index中 
  126.      * @param temp 
  127.      * @param index 
  128.      * @param table 
  129.      */  
  130.     private void setFirstEntry(Entry<K, V> temp, int index, Entry[] table) {  
  131.         // 1.判断当前容量是否超标,如果超标,调用扩容方法  
  132.         if (size > max) {  
  133.             reSize(table.length * 4);  
  134.         }  
  135.         // 2.不超标,或者扩容以后,设置元素  
  136.         table[index] = temp;  
  137.         //!!!!!!!!!!!!!!!  
  138.         //因为每次设置后都是新的链表,需要将其后接的结点都去掉  
  139.          //NND,少这一行代码卡了哥哥7个小时(代码重构)  
  140.         temp.next=null;  
  141.     }  
  142.   
  143.     /** 
  144.      * 取 
  145.      *  
  146.      * @param k 
  147.      * @return 
  148.      */  
  149.     public V get(K k) {  
  150.         Entry<K, V> entry = null;  
  151.         // 1.计算K的hash值  
  152.         int hash = k.hashCode();  
  153.         // 2.根据hash值找到下标  
  154.         int index = indexFor(hash, container.length);  
  155.         // 3。根据index找到链表  
  156.         entry = container[index];  
  157.         // 3。若链表为空,返回null  
  158.         if (null == entry) {  
  159.             return null;  
  160.         }  
  161.         // 4。若不为空,遍历链表,比较k是否相等,如果k相等,则返回该value  
  162.         while (null != entry) {  
  163.             if (k == entry.key||entry.key.equals(k)) {  
  164.                 return entry.value;  
  165.             }  
  166.             entry = entry.next;  
  167.         }  
  168.         // 如果遍历完了不相等,则返回空  
  169.         return null;  
  170.   
  171.     }  
  172.   
  173.     /** 
  174.      * 根据hash码,容器数组的长度,计算该哈希码在容器数组中的下标值 
  175.      *  
  176.      * @param hashcode 
  177.      * @param containerLength 
  178.      * @return 
  179.      */  
  180.     public int indexFor(int hashcode, int containerLength) {  
  181.         return hashcode & (containerLength - 1);  
  182.   
  183.     }  
  184.   
  185.     /** 
  186.      * 用来实际保存数据的内部类,因为采用挂链法解决冲突,此内部类设计为链表形式 
  187.      *  
  188.      * @param <K>key 
  189.      * @param <V> 
  190.      *            value 
  191.      */  
  192.     class Entry<K, V> {  
  193.         Entry<K, V> next;// 下一个结点  
  194.         K key;// key  
  195.         V value;// value  
  196.         int hash;// 这个key对应的hash码,作为一个成员变量,当下次需要用的时候可以不用重新计算  
  197.   
  198.         // 构造方法  
  199.         Entry(K k, V v, int hash) {  
  200.             this.key = k;  
  201.             this.value = v;  
  202.             this.hash = hash;  
  203.   
  204.         }  
  205.   
  206.         //相应的getter()方法  
  207.   
  208.     }  
  209. }  

 

 代码中有相当清楚的注释了

 

在文章的最后这里,我要强烈的宣泄下感情

MLGBD,本来以为分析的挺到位了,写出这个东西也就最多需要个把小时吧

结果因为通宵作业,脑袋运转不灵

硬是花了哥三个小时才写出了

好不容易些出来了

我日

看着代码比较混乱

然后就对代码重构了下

把逻辑抽象清楚,进行重构就花了个多小时

好不容易构造好了

就开始了TMD的一直报错了----------大数据量测试时到大概5000就死循环了

各种调试,各种分析都觉得没错误

 最后花了哥7个小时终于找出来了

我擦

 

第一次初始化加的时候,因为每个元素的next都是空的

而扩充容量resize()时,因为冲突处理是链式结构的

当将他们重新hash添加的时候,重复的这些鸟元素的next是有元素的

一定要设置为null

 

 

七.性能分析:

      1.因为冲突的存在,其查找长度不可能达到O(1)

      2哈希表的平均查找长度是装载因子a 的函数,而不是 n 的函数。

      3.用哈希表构造查找表时,可以选择一个适当的装填因子  ,使得平均查找长度限定在某个范围内。


  
   最后给出我们这个HashMap的性能

  测试代码

Java代码   收藏代码
  1. public class Test {  
  2.   
  3.     public static void main(String[] args) {  
  4.         MyMap<String, String> mm = new MyMap<String, String>();   
  5.         Long aBeginTime=System.currentTimeMillis();//记录BeginTime  
  6.         for(int i=0;i<1000000;i++){  
  7.         mm.put(""+i, ""+i*100);  
  8.         }  
  9.         Long aEndTime=System.currentTimeMillis();//记录EndTime  
  10.         System.out.println("insert time-->"+(aEndTime-aBeginTime));  
  11.           
  12.         Long lBeginTime=System.currentTimeMillis();//记录BeginTime  
  13.         mm.get(""+100000);  
  14.         Long lEndTime=System.currentTimeMillis();//记录EndTime  
  15.         System.out.println("seach time--->"+(lEndTime-lBeginTime));  
  16.     }  
  17. }  

  100W个数据时,全部存储时间为1S多一点,而搜寻时间为0 

 

insert time-->1536
seach time--->0

 

 

好了,牢骚发完了

本来今天想写个有关大访问量处理的一些基本概念的文章

全泡汤了,明天写吧

分享到:
评论

相关推荐

    Java实现GeoHash算法

    Java实现GeoHash算法是一种在IT领域中用于地理位置数据存储和检索的技术。GeoHash将经纬度坐标转换为字符串,使得地理位置可以被高效地索引和查询。这种算法利用了空间分割和编码策略,使得相邻的位置在编码后具有...

    geohash算法实现Java代码

    在压缩包文件"geo"中,可能包含了GeoHash算法的Java实现源代码、测试用例和其他相关资源。通过分析这些代码,我们可以深入理解GeoHash算法的工作原理,并且学习如何在实际项目中应用它。 GeoHash算法的使用场景广泛...

    Java开发中的Memcache原理及实现

    Java开发中的Memcached原理及实现主要涉及分布式缓存系统、内存管理和网络通信等多个技术领域。Memcached是一款高性能、分布式内存对象缓存系统,用于减轻数据库负载,提高网站或应用程序的响应速度。在Java环境中,...

    一致性hashjava实现

    一致性哈希(Consistent Hashing)是一种...总之,这个一致性哈希的Java实现是分布式系统中解决动态扩展和负载均衡问题的重要工具,通过理解其原理和实现细节,我们可以更好地优化分布式环境中的数据存储和访问效率。

    PersistentIdealHashTree-Java实现

    本文将深入探讨PersistentIdealHashTree的Java实现及其在并发编程中的应用。 首先,我们需要理解PersistentIdealHashTree的基本概念。这种数据结构是一种基于哈希表的持久化数据结构,其核心特点是能够在保持旧版本...

    Java实现相似图片搜索原理 源码分享

    Java实现相似图片搜索原理 源码分享。 Google "相似图片搜索":你可以用一张图片,搜索互联网上所有与它相似的图片。 这种技术的原理是什么?计算机怎么知道两张图片相似呢? 根据Neal Krawetz博士的解释,原理非常...

    相似图片搜索原理 Java实现源码

    这里的关键技术叫做"感知哈希算法"(Perceptual hash algorithm),它的作用是对每张图片生成一个"指纹"(fingerprint)字符串,然后比较不同图片的指纹。结果越接近,就说明图片越相似。 这是一个最简单的实现。

    数据库管理系统(java实现)

    数据库系统原理实验 数据库管理系统...文件存储表、库,根据sql语句实现建表,建库 可以建立索引(B+树) 可以做笛卡尔积(hash) 自然连接(哈弗曼树)等 有查询树结构 可以完成登录权限管理。 下载后有问题可以联系我。

    深入Java集合学习系列:HashMap的实现原理

    在Java编程语言中,集合框架是开发者日常工作中不可或缺的一部分,HashMap作为其中的重要成员,它的实现原理对于理解Java性能优化和数据结构有深远的意义。HashMap是一个基于哈希表的数据结构,它实现了Map接口,...

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

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

    Android-java中的Geohash工具类

    本文将深入探讨Geohash的工作原理,如何在Java中实现以及在Android开发中的应用。 首先,我们来理解什么是Geohash。Geohash是由美国科学家Doug Lindsay在2008年提出的,基于分形几何和基数编码的一种地理位置编码...

    java-Hash算法大全.doc

    本文将对 Java 中的哈希算法进行详细的介绍,包括加法哈希、旋转哈希、一次一个哈希、Bernstein 哈希、Pearson 哈希、CRC 哈希、Universal 哈希等七种哈希算法的实现和原理。 一、加法哈希(Additive Hash) 加法...

    ConsistentHash:一致性hash算法的 java 和 C++ 实现

    在这个场景下,我们将深入探讨一致性哈希算法的原理、特点以及在Java和C++中的实现。 一致性哈希算法的基本思想是将哈希空间环绕成一个虚拟的圆环,每个节点都被分配到这个环上的一个或多个位置。当需要将数据映射...

    相似图片搜索原理源码-Java实现

    这里的关键技术叫做"感知哈希算法"(Perceptual hash algorithm),它的作用是对每张图片生成一个"指纹"(fingerprint)字符串,然后比较不同图片的指纹。结果越接近,就说明图片越相似。 这是一个最简单的实现。

    【IT十八掌徐培成】Java基础第11天-03.Map集合-hash原理2.zip

    在本课程“【IT十八掌徐培成】Java基础第11天-03.Map集合-hash原理2”中,我们将深入探讨Map集合的内部机制,特别是哈希(Hash)原理的应用。这个课程的视频文件名为“Java基础第11天-03.Map集合-hash原理2.avi”。 ...

    java源码:哈希计算工具 java-hash.7z

    这个"java-hash.7z"压缩包包含了一个Java实现的哈希计算工具,这是一份经典的学习资源,可以帮助开发者深入理解哈希算法及其在Java中的应用。 哈希(Hash)函数是一种将任意长度输入(也叫做预映射pre-image)通过...

    MD5加密算法的JAVA实现

    本文将深入探讨MD5算法在Java中的实现方式,包括其原理、代码实现以及应用场景。 ### MD5算法原理 MD5(Message-Digest Algorithm 5)是由Ron Rivest于1992年设计的一种散列算法,用于将任意长度的消息压缩成一个...

    哈希表的原理 数据结构

    哈希表(Hash Table)是一种常用的数据结构,它的原理是通过哈希函数(Hash Function)将关键码值映射到表中一个位置,以加快查找的速度。哈希表的优点是其理想算法复杂度为 O(1),即利用哈希表查找某个值,系统所...

    【IT十八掌徐培成】Java基础第11天-02.Map集合-hash原理.zip

    在本课程“【IT十八掌徐培成】Java基础第11天-02.Map集合-hash原理”中,将深入探讨Map集合以及其背后的哈希原理。 Map接口不继承Collection接口,而是独立的一类数据结构,其核心方法包括put()用于添加键值对,get...

Global site tag (gtag.js) - Google Analytics