首页 > 代码库 > Hash(4) hashtable,hashmap

Hash(4) hashtable,hashmap

 

首先,我们要知道set是利使用map是实现的,因为只要利用map中的key唯一性就行了。

1.hashmap 和hashtable的区别是什么?

我们可以背出:  hashtable线程安全。hashmap不安全。

                        hashmap中key 和value可以为空,当然根据唯一性,只能有一个key为null;

                       还有呢,hash函数不同下面再谈)

2.我们在知识点回顾中,对于一个hash函数,有哪些方法,如何解决冲突/

 除留余数法(最常用),平方取中,随机数法

开放地址法,拉链法

3、那么hashmap中和hashtablehash函数是什么呢?如何解决冲突的呢。

解决冲突是拉链法,就是加链表。

那么hash函数呢,

hashmap 比较高级,我们看hashmap,如果你复习一下数据结构,在哈希表中,他会告诉你,一个hash表就是个数组,这个数组有大小,同时还有装载因子,

size*loadFactor就是我们能存元素个数的最大值,这个值叫做阈(yu)值,超过这个值,就会resize,意思就是重新扩张数组,然后对老元素重新hash,所以resize很费时。

hashmap在size上下了功夫,他把数组的大小设置为2的n次方,初始为16.,如果不够用就成2倍扩张。为什么设置为2的n次方呢?

这样可以充分利用位运算的优势。比如 a*2  表示成  a<<1, 那么 a%16=a&1 5=a&(1111)=a的二级制的后面4为,在位图中我们a%32=a&31

其实如果我们看 a&1=a%2  a&3=a%4  好了,下面我们看看它的hash函数吧

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

 看到没有直接风骚的使用h&(length-1)而且length是2的倍数。其实就是h%(length)

慢着,这个函数有什么缺陷呢?当size比较小的时候,比如32的时候,也就是(11111),最后根据key确定位置的时候,是根据key的后5位确定的,而key,函数中使用h表示,是int型啊,32位的数只能通过后五位确定,这样冲突会很多,我们希望32位的每一位都被考虑进来。都可以决定key的位置,于是,

1     static int hash(int h) {2         // This function ensures that hashCodes that differ only by3         // constant multiples at each bit position have a bounded4         // number of collisions (approximately 8 at default load factor).5         h ^= (h >>> 20) ^ (h >>> 12);6         return h ^ (h >>> 7) ^ (h >>> 4);7     }

我们看到了,这个复杂的代码,它的意思就是我刚才说的,通过移位和异或让更多的位决定key的位置,这样会减少冲突,更均匀。

但是hashtable,虽说是线程安全的,但是他是jdk1.0引入的很老,它的hash函数很普通,

int index = (hash & 0x7FFFFFFF) % tab.length; //hash就是key的hashcode,然后获得非符号位(hashcode为 int,可能为负,所以去掉符号位);

对于线程安全,以后再仔细说。

 

 

 

 

 

 

 

 

 

 

 

 

 

http://zhangshixi.iteye.com/blog/672697