Set散列表

code_money_guji posted @ 2011年2月25日 05:00 in 算法/数据结构 , 939 阅读

参考资料:

Java核心技术[I]

<<数据结构>> ----严蔚敏

wiki http://zh.wikipedia.org/wiki/%E6%95%A3%E5%88%97%E8%A1%A8

http://www.ibm.com/developerworks/java/library/j-jtp05273.html java equals() and hasCode()

http://www.partow.net/programming/hashfunctions/ 各种各样的 hashCode 算法,相当犀利.

散列表原理:

wiki 中队散列表的概念描述如下:

若结构中存在关键字和K相等的记录，则必定在f(K)的存储位置上。由此，不需比较便可直接取得所查记录。称这个对应关系f(Hash function)，按这个思想建立的表为散列表。
对不同的关键字可能得到同一散列地址，即key1≠key2，而f(key1)=f(key2)，这种现象称冲突。具有相同函数值的关键字对该散列函数来说称做同义词。综上所述，根据散列函数H(key)和处理冲突的方法将一组关键字映象到一个有限的连续的地址集（区间）上，并以关键字在地址集中的“象”作为记录在表中的存储位置，这种表便称为散列表.
若对于关键字集合中的任一个关键字，经散列函数映象到地址集合中任何一个地址的概率是相等的，则称此类散列函数为(Uniform Hash function)，这就是使关键字经过散列函数得到一个“随机的地址”，从而减少冲突.

Hash函数的构造方法；

1 直接定址:

H(key) = key or H(key) = a*key +b

从上面的Hash Function看出,直接定地址的方式构造的hash Function 不会带来hash 冲突, 有多少个key就有多少个hash值对应.

2 数字分析:

H(key) = choose(bits in keys) 也就是根据已知的key来进行分析, 选择合适的几个冲突较小的位数作为hash地址.

这个算法缺点就是知道key的具体范围以及能够分析出一个冲突比较小的数值规律. 例如:

1bit 2bit 3bit 4bit

0 1 2 7

1 1 3 8

0 1 4 9

0 0 5 0

0 1 6 5

以上是四位以十进制为基数的hash key, 可选择 (4bit 和 3 bit)为组合来制定has地址.

3 平均取中:

hash(key) = chooseMiddle(Math.sqrt(key)) 看时机情况定chhseMiddle函数取几位.

4 除留余数法:

若hashTale.length = M, 那么H(key) = key MOD p , p <= M

一般来说: p选择一个质数或者不包括小于20的质因数的合数

5 随机数法

Hash 函数实现:

java.lang.String:

        int h = hash;
        int len = count;//count 为string的长度
	if (h == 0 && len > 0) {
	    int off = offset; //string 的偏移量
	    char val[] = value; //value几位String 中的内置 char[]

            for (int i = 0; i < len; i++) {
                h = 31*h + val[off++];
            }
            hash = h;
        }
        return h;

AbstractArrayList:

             int hashCode = 1;
	Iterator<E> i = iterator();
	while (i.hasNext()) {
	    E obj = i.next();
	    hashCode = 31*hashCode + (obj==null ? 0 : obj.hashCode());//会调用相关对象的hashCode
	}
	return hashCode;

java 中推荐的eauls 以及hasCode的自定义实现:

 public boolean equals(Object other) {
    // Not strictly necessary, but often a good optimization 先把不耗时间的步骤完成, 注意这部分的代码重构;
    if (this == other)
      return true;
    if (!(other instanceof A))
      return false;
    A otherA = (A) other;
    return 
      (someNonNullField.equals(otherA.someNonNullField))
        && ((someOtherField == null) 
            ? otherA.someOtherField == null 
            : someOtherField.equals(otherA.someOtherField)));
  }


-----------------------------

public int hashCode() { 
    int hash = 1;
    hash = hash * 31 + someNonNullField.hashCode();
    hash = hash * 31 
                + (someOtherField == null ? 0 : someOtherField.hashCode());
    return hash;
  }

如果觉得上述的讲述不够爽,那么建议你阅读:http://www.partow.net/programming/hashfunctions/

上述的建议是将hashCode和equals一起完成,为什么？如果你使用的是几个基于Hash的容器来管理的呢Entity，当使用contains(),get()之类的方法,那么就应该view一下这些HashSet和HashMap的一个方法实现，下面是HashSet中contains()方法: [其实,HashSet是基于HashMap]:

HashSet 的 contains方法:
return map.containsKey(o);
//map是一个HashMap,可见HashSet是基于HashMap的

 public boolean containsKey(Object key) {
        return getEntry(key) != null;
    }
---------------------进入getEntity(key)
 final Entry<K,V> getEntry(Object key) {
        int hash = (key == null) ? 0 : hash(key.hashCode());
        for (Entry<K,V> e = table[indexFor(hash, table.length)];
             e != null;
             e = e.next) {
            Object k;
            if (e.hash == hash &&
                ((k = e.key) == key || (key != null && key.equals(k))))
                return e;
        }
        return null;
    }

这个方法先得到对象在HashMap中的位置,通过indexFor(hash)方法找到对象,最后再比较找到的对象和需要查找的对象之间的equals方法.

散列表的数据结构实现 :

需要解决的问题: 当上面介绍的hash function 出现冲突的时候,如何存储相关的值.【即解决hash冲突】

hash冲突的解决方案:

开放寻址法；Hi=(H(key) + di) MOD m, i=1,2,…, k(k<=m-1)，其中H(key)为散列函数，m为散列表长，di为增量序列，可有下列三种取法：
1. di=1,2,3,…, m-1，称线性探测再散列；
2. di=1^2, (-1)^2, 2^2,(-2)^2, (3)^2, …, ±(k)^2,(k<=m/2)称二次探测再散列;
3. di=伪随机数序列，称伪随机探测再散列。 ==
再散列法：Hi=RHi(key), i=1,2,…,k RHi均是不同的散列函数，即在同义词产生地址冲突时计算另一个散列函数地址，直到冲突不再发生，这种方法不易产生“聚集”，但增加了计算时间。
链地址法（拉链法）
建立一个公共溢出区

java 散列表[SET]数据结构[使用链地址法解决]:

java 中是使用链表数组来实现,每一个链表称为一个bucket.处理过程是首先找到需要查的对象的bucket散列码,具体是与bocket.length取余数, 前面提到每一个bucket是一个链表, 然后开始循环列表来查找.

但bucket太小的时候,冲突会比较大. 一般定在预计元素的 75%---150%[load factor]. 现实中大部分的时候可能无法预见插入个数有多少,当现有的bucket太小的时候,需要通过"再散列"的方式来重新构造表的bucket大小,并将现有的元素重新查到新的hash table中. load factor 填装因子决定了何时构造新的hash table. 当现有的元素 > load factor.就进行新的表构造.

java 的HashMap就是这样的一个数据结构, HashMap中有一个Entity[]数组,每一个 Entity是一个 <K,V>的链表结构.

TreeSet 的数据结构则不一样,是一个基于红黑树的结构, 每一次将新的元素插入到树中的时候,都要进行相关的排序工作,所以使用TreeSet的插入性能要比HashSet高一些.

也正是因为有排序在,所以,使用TreeSet是可以进行排序的. TreeSet的实现是通过TreeMap来实现的.TreeMap中持有一个Entity<K,V> root表示树的根节点.下面是TreeMap的put(....)方法实现:

 Entry<K,V> t = root;
             ...处理root == null...
        int cmp;
        Entry<K,V> parent;
        // split comparator and comparable paths
        Comparator<? super K> cpr = comparator;
        if (cpr != null) {
            do {
                parent = t;
                cmp = cpr.compare(key, t.key);
                if (cmp < 0)
                    t = t.left;
                else if (cmp > 0)
                    t = t.right;
                else
                    return t.setValue(value);
            } while (t != null);
        }
        else {
            if (key == null)
                throw new NullPointerException();
            Comparable<? super K> k = (Comparable<? super K>) key;
            do {
                parent = t;
                cmp = k.compareTo(t.key);
                if (cmp < 0)
                    t = t.left;
                else if (cmp > 0)
                    t = t.right;
                else
                    return t.setValue(value);
            } while (t != null);
        }
        Entry<K,V> e = new Entry<K,V>(key, value, parent);
        if (cmp < 0)
            parent.left = e;
        else
            parent.right = e;
        fixAfterInsertion(e);
        size++;
        modCount++;
        return null;

是否能够看出些树的影子? 呵呵.

【友情提示:优先级队列是基于堆的数据结构实现,其实学习集合类可以顺便学习数据结构.】

<to be continue ... >

code_money_guji's Blog

Happy coding

Set散列表

code_money_guji

分类

最新评论

最新留言

链接

RSS

功能