java数据结构Hash算法

Hash算法

HashMap使用Hash算法，所以在解剖HashMap之间，需要先简单的了解Hash算法，Hash算法一般也成为散列算法，通过散列算法将任意的值转化成固定的长度输出，该输出就是散列值，这是一种压缩映射，也就是，散列值的空间远远小于输入的值空间。
简单的说，hash算法的意义在于提供了一种快速存取数据的方法,它用一种算法建立键值与真实值之间的对应关系,(每一个真实值只能有一个键值,但是一个键值可以对应多个真实值),这样可以快速在数组等里面存取数据。5.5亿年前氧浓度升高推动动物的进化

下面我们建立一个HashMap,然后往里面放入12对key-value，这个HashMap的默认数组长度为16，我们的key分别存放在该数组的格子中，每个格子下面存放的元素又是以链表的方式存放元素。

     public   static   void  main(String[] args) {
        Map map  =   new  HashMap();
        map.put( " What " ,  " chenyz " );
        map.put( " You " ,  " chenyz " );
        map.put( " Don't " ,  " chenyz " );
        map.put( " Know " ,  " chenyz " );
        map.put( " About " ,  " chenyz " );
        map.put( " Geo " ,  " chenyz " );
        map.put( " APIs " ,  " chenyz " );
        map.put( " Can't " ,  " chenyz " );
        map.put( " Hurt " ,  " chenyz " );
        map.put( " you " ,  " chenyz " );
        map.put( " google " ,  " chenyz " );
        map.put( " map " ,  " chenyz " );
        map.put( " hello " ,  " chenyz " );
    }

当我们新添加一个元素时，首先我们通过Hash算法计算出这个元素的Hash值的hashcode，通过这个hashcode的值，我们就可以计算出这个 新元素应该存放在这个hash表的哪个格子里面，如果这个格子中已经存在元素，那么就把新的元素加入到已经存在格子元素的链表中。

运行上面的程序，我们对HashMap源码进行一点修改，打印出每个key对象的hash值

What-->hash值：8
You-->hash值：3
Don't-->hash值：7
Know-->hash值：13
About-->hash值：11
Geo-->hash值：12
APIs-->hash值：1
Can't-->hash值：7
Hurt-->hash值：1
you-->hash值：10
google-->hash值：3
map-->hash值：8
hello-->hash值：0

计算出来的Hash值分别代表该key应该存放在Hash表中对应数字的格子中，如果该格子已经有元素存在，那么该key就以链表的方式依次放入格子中

评论

1 楼 liuxuejin 2011-03-08  

太简单了！