Hash构造

Hash结构
关于HashMap  在http://www.iteye.com/topic/754887这篇文章中有做比较好的讲解
下面是我在一些点上自己的看法。
我们会经常使用HashMap类来进行存储数据，HashMap<K k,V v>map = new HashMap<K k,V v>();对于Map我们经常使用的也就是put(k,v);remove();search();这三个方法，我们添加数据到HashMap结构中，只觉得它用起来还不错，但它不错在哪？
   一,Hash结构有什么优势？
   我们知道数组是便于查找，因为它的下标，而链表便于添加和删除，（修改地址指向），但是对于很多个数，比如上亿，如果我们用数组来存储这么多数，如果我们要删除其中的一个元素，我们将会移动N个，同样用在链表查找的时候也很费劲。Hash结构中的拉链式（书上的名词）是结合数组和链表的一种存储结构（还有一种叫开放定址法）通过数组的下标设成Index索引，把结点挂在数组Entry[]上，Hash结构的优势在于它既便于查找，也在删除和添加上较快。
   二，我对HashMap的浅析
   1)

 static class Entry<K,V> implements Map.Entry<K,V> {        final K key;//关键字        V value;//存储的数据数值        Entry<K,V> next;//在解决冲突的时候，创建链表的时候使用，表示下一个结点。        final int hash;

  HashMap用Entry类来存储数据，HashMap中数组的默认长度是16
  2）看到上面的hash没，我吧下面段编码放在一起，这样更便于我们的理解

         static int hash(int h) {        h ^= (h >>> 20) ^ (h >>> 12);        return h ^ (h >>> 7) ^ (h >>> 4);        }

          

int hash = hash(k.hashCode());int i = indexFor(hash, table.length);

  

static int indexFor(int h, int length) {        return h & (length-1);    }

hash值是通过Key的hashCode()（hash编码）得来的，i是要存入数据的索引地址，HashMap中的索引是用与运算得到，我们也可以用别的方法，比方说取模 % 。为什么要把hash值和（length+1）做与运算，而不是用（length）呢！这是官方通过实验调查得出结论，官方上说 奇数比偶数要好，理论研究表明:length-1取不大于数组长度的素数效果最好。
  3）Hash冲突，解决方法
   上面讲到了Hash冲突，那么我们会在什么时候遇到Hash冲突呢，打个比方：我们现在有初始状态下的数组，数组的长度是16，当我们添加20元素，通过取模1和17的索引就相同了，这就叫Hash冲突。
   解决Hash冲突 ， 上面讲过一点，我们通过子添加结点，把冲突的元素挂在链表上Entry<K,V> next 
下面是我的添加结点的方法

Entry<k,v>node = new node<k,v>();index=Indexfo(hash,table.length);node.next=table[index].next;table[index].next =node;

冲突是一个问题，但还有另一个问题，如果添加的元素都是具有同一个索引，那么我们就会把他一直的往链表上挂，那么我们得到的就会非常的偏向于链表，我们的Hash表就没有什么优势存在，所以我们需要控制每个链表的长度，也就是设置一个阀值，用来使得我们的Hash表存储的数据分布尽量的均匀。
4)如何使得分布均匀
我们通过给链表加一个长度计数变量，在添加元素的时候进行判断，如果链表的长度超过我们设定的阀值，那么我们就重新设置我们的数组的长度

在HashMap中有这么一个方法

resize(int newCapacity){...transfer(newTable);//转移原数组的元素到新的数组...}

我们在调用resize(n)是，这个n可以设定为原数组的2倍或其他
在上面我们看到了transfer(newTable);这个方法这个方法是用来进行转移的
我们知道数组在内存中的开辟地址的，他的大小我们是不改变的，所以我们要用到transfer(newTable);这个方法，这个方法有必要记住，在以后我们使用的时候随手捏来

void transfer(Entry[] newTable) {        Entry[] src = table;        int newCapacity = newTable.length;        for (int j = 0; j < src.length; j++) {            Entry<K,V> e = src[j];            if (e != null) {                src[j] = null;                do {                    Entry<K,V> next = e.next;                    int i = indexFor(e.hash, newCapacity);                    e.next = newTable[i];                    newTable[i] = e;                    e = next;                } while (e != null);            }        }    }

这个方法是扩展数组的长度
5） 在HashMap中有一个变量  loadFactor  这个叫做 比例因子
这个的用法是在我们设置阀值的时候用到
HashMap中

threshold = (int)(newCapacity * loadFactor);

这个就是设置阀值   在HashMap中loadFactor  的取值是0.75，官方给出了一个取值范围0.6~0.9  这样的效果是比较好的，到底好在哪里？我测试不出，如果你们有兴趣，可以自己想个方法测试一下，前提，你的电脑性能要好。
    到此一个Hash表的结构基本可以了，有不足的地方希望大家能够指出。文章应该写些什么，也希望大家给意见。

查看更多 下一篇