首页 > 代码库 > HashMap二三事
HashMap二三事
先看看hashmap在整个Collection中的位置
HashMap中存储数据的结构是
/**
* The table, resized as necessary. Length MUST Always be a power of two.
*/
transient Entry<K,V>[] table;上面的英文就不用说了。
原来基础的存储结构式Entry的数组!
至于Entry是HashMap的一个内部类
static class Entry<K,V> implements Map.Entry<K,V> {
final K key;
V value;
Entry<K,V> next;
int hash;
/**
* Creates new entry.
*/
Entry(int h, K k, V v, Entry<K,V> n) {
value = http://www.mamicode.com/v;>
看到里面的这个参数Entry<K,V> next大家应该都明白了,HashMap中每个Entry键值对都是一个链表!!!
下面我们看看map的put,get,iterator方法及遍历
put方法
public V put(K key, V value) {
if (key == null)
return putForNullKey(value);
//计算key的hash 里面的实现比较麻烦 可以不用理会
int hash = hash(key);
//由hash码得到存储位置 计算方法是hash与table.length-1相与 这样的好处就是能保证要存放的位置肯定不会超过table的范围
//前面的hash方法与indexFor 我没有仔细研究 不过大家可以认为 两个不同的hash会对应不同的存储位置
int i = indexFor(hash, table.length);
//e.next 链表
//如果i的位置上已经有元素了 继续看for循环
//否则就new一个新的Entry
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
//如果要存储的key的hash值与已经存在在那个位置元素的key的hash值相等 并且两个key的内容也相等
//话说这里我看的不是太懂 e本身是一个新的对象
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = http://www.mamicode.com/e.value;>
什么时候table[bucketIndex]里面才有数据呢? 换句话说拉链法是怎么实现的呢?我们先看下面的遍历。
hashmap的遍历
package iterator;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Random;
import java.util.Iterator;
import java.util.HashMap;
import java.util.Collection;
/*
* @desc 遍历HashMap的测试程序。
* (01) 通过entrySet()去遍历key、value，参考实现函数：
* iteratorHashMapByEntryset()
* (02) 通过keySet()去遍历key、value，参考实现函数：
* iteratorHashMapByKeyset()
* (03) 通过values()去遍历value，参考实现函数：
* iteratorHashMapJustValues()
*
* @author skywang
*/
public class HashMapIteratorTest {
public static void main(String[] args) {
int val = 0;
String key = null;
Integer value = http://www.mamicode.com/null;>拉链法
上面已经说了使用entrySet的方式效率高,大家以后就采用这个吧,另外还提到了什么时候用拉链法看下面这个例子
HashMap<Person, Integer> map = new HashMap<Person, Integer>();
map.put(new Person("dlf", 14),12);
map.put(new Person("dlf", 15),12);
map.put(new Person("sdfe", 16),12);
对于person这个类,我重写了hashCode方法,但是没有重写equals方法;
person的hashCode方法:
public int hashCode() {
int h = 0;
if (name.equals("dlf")) {
return 123456789;
}
if (h == 0 && value.length > 0) {
char val[] = value;
for (int i = 0; i < value.length; i++) {
h = 31 * h + val[i];
}
hash = h;
}
return h;
}
大家再看看hashMap里面的put方法
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
//如果要存储的key的hash值与已经存在在那个位置元素的key的hash值相等 并且两个key的内容也相等
//话说这里我看的不是太懂 e本身是一个新的对象
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = http://www.mamicode.com/e.value;>当我
map.put(new Person("dlf", 14),12);
map.put(new Person("dlf", 15),12);
第二个person的hashcode与第一个person的hashcode是一样的,但是看看上面if条件句的第二部分
(k = e.key) == key || key.equals(k)
此时调用Object的equals方法也就是==,那么==比较的是什么呢?栈里面存储的地址值,两个新new处理的对象地址那自然不同的,所以if条件不满足,跳出for循环;
最后的结果是
iterator HashMap By entryset
dlf 15 -- 12
dlf 14 -- 12
sdfe 16 -- 12
iterator HashMap By keyset
dlf 15 -- 12
dlf 14 -- 12
sdfe 16 -- 12
12
12
12
get方法
public V get(Object key) {
if (key == null)
return getForNullKey();
// 获取key的hash值
int hash = hash(key.hashCode());
// 在“该hash值对应的链表”上查找“键值等于key”的元素 大家看到了 是在hash对应的位置查找,而不是查找整个table
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.equals(k)))
return e.value;
}
return null;
}
iterator方法
我们就看效率最高的entrySet方法
Set<Entry<Person, Integer>> set=map.entrySet(); //为了更清楚些 我分开写
Iterator<?> iter = set.iterator();
最开始调用entrySet方法的时候,entrySet对象还为null,会调用new EntrySet;
待得到set集合后,会再次调用iterator方法
public Set<Map.Entry<K,V>> entrySet() {
return entrySet0();
}
private Set<Map.Entry<K,V>> entrySet0() {
Set<Map.Entry<K,V>> es = entrySet;
return es != null ? es : (entrySet = new EntrySet());
}
private final class EntrySet extends AbstractSet<Map.Entry<K,V>> {
public Iterator<Map.Entry<K,V>> iterator() {
return newEntryIterator();
}
.......
}
Iterator<Map.Entry<K,V>> newEntryIterator() {
return new EntryIterator();
}
大家看到了最后返回的Iterator是一个EntryIterator。
看EntryIterator的代码,它是继承了HashIterator;
private final class EntryIterator extends HashIterator<Map.Entry<K,V>> {
public Map.Entry<K,V> next() {
return nextEntry(); //这个方法在HashIterator中定义
}
}随后我们在程序里调用
Map.Entry<Person, Integer> entry = (Entry<Person, Integer>)iter.next();
//以下为HashIterator类
//构造函数
//在我们new EntryIterator的时候 就已经调用这个其父类HashIterator的构造函数了
//HashIterator的成员变量在构造函数里面 就已经指到table里第一个元素了
HashIterator() {
expectedModCount = modCount;
if (size > 0) { // advance to first entry
Entry[] t = table;
while (index < t.length && (next = t[index++]) == null)
;
}
}
final Entry<K,V> nextEntry() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
Entry<K,V> e = next; //这个next是构造函数里面就指到table里第一个元素了(第一个不为null的元素)
if (e == null)
throw new NoSuchElementException();
// 先让next=e.next 然后才判断next是否为空
if ((next = e.next) == null) {
//从第一行调用来看
//如果table的第一个Entry(其实就是一个单链表) 就只有一个元素(其next为空)
//让next找到table的下一个元素
Entry[] t = table;
while (index < t.length && (next = t[index++]) == null)
;
}
current = e;
return e;
}
有了上面的if ((next = e.next) == null) 这一行,我们就不仅能遍历整个table,还能将table中某个entry中的所有元素也遍历了!不重复,不遗漏。
参考资料
http://www.cnblogs.com/skywang12345/p/3310835.html
我多说两句,上面的博客把java的整个Collection的源代码剖析了一遍,博客主人真乃牛人呀! 大家一定要去看看
HashMap二三事
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。