学习java中的几个Map-我们到底能走多远系列(27)

来源:互联网 时间:1970-01-01

我们到底能走多远系列(27)

扯淡:

你现在的工作过程是否利于个人成长呢?

你能直接在工作中学到大量刚兴趣的东西吗?

你的爱好都是在业余时间学习的吗?

你加班的时间是否已经影响了你对编程学习的兴趣?

 

主题:

Hashtable 提供了一种易于使用的、线程安全的map功能,Hashtable 中所有操作方法都是同步的,所以性能较于非线程安全的HashMap就下降了。两者的结构差不多,先有一个数组,数组的每一位存链表。如图:这就是他们的数据结构啦。看一些源码:构造函数:
 public Hashtable( int initialCapacity, float loadFactor) { if (initialCapacity <= 0) initialCapacity = 11; if (loadFactor <= 0.0) loadFactor = 0.75f; this.loadFactor = loadFactor; table = new HashtableEntry[initialCapacity]; threshold = (int )(initialCapacity * loadFactor); }
threshold = 数组范围(initialCapacity )* 装载因子(loadFactor)所以如果初始化map的时候限定100的范,那么75就是界限。 根据这个结构我们来看看存取数据的源码,可以看出两者之间的一些区别。 首先是Hashtable 的:
public synchronized V put(K key, V value) { // Make sure the value is not null // Hashtable 不支持null作为key if (value == null) { throw new NullPointerException(); } // Makes sure the key is not already in the hashtable. Entry tab[] = table; int hash = hash(key); int index = (hash & 0x7FFFFFFF) % tab.length ; // 像数组中放数据,如果已经有值,则以链表的型式加入末端 for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) { if ((e.hash == hash) && e.key.equals(key)) { V old = e. value; e. value = value; return old; } } modCount++; if (count >= threshold ) { // Rehash the table if the threshold is exceeded // 重新定义数组长度,对所有的hashcode进行重新设置 rehash(); tab = table; hash = hash(key); index = (hash & 0x7FFFFFFF) % tab. length; } // Creates the new entry. Entry<K,V> e = tab[index]; tab[index] = new Entry<>(hash, key, value, e); count++; return null ; }public synchronized V get(Object key) { Entry tab[] = table; int hash = hash(key); int index = (hash & 0x7FFFFFFF) % tab.length ; // 根据下标地址查询数据 for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) { if ((e.hash == hash) && e.key.equals(key)) { return e.value ; } } return null ; }

 

下面是HashMap的存取源码:
 public V put(K key, V value) { // HashMap 支持null作为key if (key == null ) return putForNullKey(value); int hash = hash(key); int i = indexFor(hash, table. length); for (Entry<K,V> e = table [i]; e != null; e = e.next) { Object k; if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { V oldValue = e. value; e. value = value; e.recordAccess( this); return oldValue; } } modCount++; // 拆出去的方法,利于子类的自定义实现 addEntry(hash, key, value, i); return null ; } void addEntry( int hash, K key, V value, int bucketIndex) { if ((size >= threshold ) && (null != table[bucketIndex])) { // 扩大2倍 resize(2 * table. length); hash = ( null != key) ? hash(key) : 0; bucketIndex = indexFor(hash, table.length); } createEntry(hash, key, value, bucketIndex); } public V get(Object key) { if (key == null ) return getForNullKey(); Entry<K,V> entry = getEntry(key); return null == entry ? null : entry.getValue();// 拆出去的方法 } final Entry<K,V> getEntry(Object key) { int hash = (key == null) ? 0 : hash(key); 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 ; }

 

一些理解:

1,从上面的代码看map的结构基本相同,我们会注意到,如果在插入数据的时候,这些数据平均的分配到数组上,也就是说没有产生链表的数据结构,那么在取得这个数据是通过地址查询的,如果出现最坏的情况,那就是大多或所有的数据的hashcode都相同,导致所有的数据都存在某个数组下标下的链表结构上,那么这个链表会变得很大,如此每次查询最坏的是遍历查询,也就失去的map的意义。所以在操作的时候,链表中的元素越多,效率越低,因为要不停的对链表循环比较。所以,一定要哈希均匀分布,尽量减少哈希冲突,减少了哈希冲突,就减少了链表循环,就提高了效率。这个问题就肯呢过会引起:Hash Collision DoS来自   http://coolshell.cn/articles/6424.html  的描述:

无论你用JSP,PHP,Python,Ruby来写后台网页的时候,在处理HTTP POST数据的时候,你的后台程序可以很容易地以访问表单字段名来访问表单值,就像下面这段程序一样:

12$usrname=$_POST['username'];$passwd=$_POST['password'];

这是怎么实现的呢?这后面的东西就是Hash Map啊,所以,我可以给你后台提交一个有10K字段的表单,这些字段名都被我精心地设计过,他们全是Hash Collision ,于是你的Web Server或语言处理这个表单的时候,就会建造这个hash map,于是在每插入一个表单字段的时候,都会先遍历一遍你所有已插入的字段,于是你的服务器的CPU一下就100%了,你会觉得这10K没什么,那么我就发很多个的请求,你的服务器一下就不行了。

举个例子,你可能更容易理解:

如果你有n个值—— v1, v2, v3, … vn,把他们放到hash表中应该是足够散列的,这样性能才高:

0 -> v2
1 -> v4
2 -> v1


n -> v(x)

但是,这个攻击可以让我造出N个值——  dos1, dos2, …., dosn,他们的hash key都是一样的(也就是Hash Collision),导致你的hash表成了下面这个样子:

0 – > dos1 -> dos2 -> dos3 -> …. ->dosn
1 -> null
2 -> null


n -> null

于是,单向链接就这样出现了。这样一来,O(1)的搜索算法复杂度就成了O(n),而插入N个数据的算法复杂度就成了O(n^2),你想想这是什么样的性能。

 

2,还注意到,map中的数组是有长度的,当放入的数据足够多,就是满足了Hashtable 的 count >= threshold (threshold上面已经提到过)HashMap 的 size >= threshold会导致Hashtable执行rehash(),HashMap会执行resize(2 * table. length)而这两个方法是很耗时,因为他们要对每一个数据重新计算hashcode,重新计算在数组中的位置。 关于resize会出现的问题:http://coolshell.cn/articles/9606.html  关于LinkedHashMap: 有时候在实现业务的时候我们需要一个有序的Map,可能会想到LinkedHashMap事实上 它继承了HashMap,自己维护了一个双向链表,以保存数据的顺序。看一下他的增加数据的方法:
 void addEntry( int hash, K key, V value, int bucketIndex) { super .addEntry(hash, key, value, bucketIndex); // Remove eldest entry if instructed Entry<K,V> eldest = header. after; if (removeEldestEntry(eldest)) { removeEntryForKey(eldest. key); } }
addEntry方法在hashMap中是在put公共方法中调用的(前面源码提到),先走了父类的代码然后自己实现字方法,里面就是在链表上维持顺序,如此,当要取出来的时候就可以更具这个链表得到顺序的数据了。    

让我们继续前行

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

努力不一定成功,但不努力肯定不会成功。

共勉。

 

相关阅读:
Top