HashMap - juedaiyuer/researchNote GitHub Wiki

##hashMap笔记##

hashmap

Java HashMap工作原理及实现(evernote)

public class hashmap {

	public static void main(String[] args) {
		HashMap<String, Integer> map = new HashMap<String, Integer>();
		map.put("语文", 1);
		map.put("数学", 2);
		map.put("英语", 3);
		map.put("历史", 4);
		map.put("政治", 5);
		map.put("地理", 6);
		map.put("生物", 7);
		map.put("化学", 8);

		//增强的for循环；entrySet实现了Set接口,里面存放了键值对k-v
		for(Entry<String, Integer> entry : map.entrySet()) {
		    System.out.println(entry.getKey() + ": " + entry.getValue());
		}
	}
}

HashMap参数,容量Capacity,负载因子Load factor。这两个参数影响HashMap性能的重要参数

哈希表

hash

哈希表是如何确定自己存储到哪一个数组节点中

key%len

hashmap随机存取

//存储时:
int hash = key.hashCode();// 这个hashCode方法这里不详述,只要理解每个key的hash是一个固定的int值
int index = hash % Entry[].length;
Entry[index] = value;

//取值时:
int hash = key.hashCode();
int index = hash % Entry[].length;
return Entry[index];

##源码分析##

// HashMap构造函数源码
public HashMap(int initialCapacity, float loadFactor) {
	    //初始容量不能<0
	    if (initialCapacity < 0)
	        throw new IllegalArgumentException("Illegal initial capacity: "
	                + initialCapacity);
	    //初始容量不能 > 最大容量值，HashMap的最大容量值为2^30
	    if (initialCapacity > MAXIMUM_CAPACITY)
	        initialCapacity = MAXIMUM_CAPACITY;
	    //负载因子不能 < 0
	    if (loadFactor <= 0 || Float.isNaN(loadFactor))
	        throw new IllegalArgumentException("Illegal load factor: "
	                + loadFactor);

	    // 计算出大于 initialCapacity 的最小的 2 的 n 次方值。
	    int capacity = 1;
	    while (capacity < initialCapacity)
	        capacity <<= 1;
	    
	    this.loadFactor = loadFactor;
	    //设置HashMap的容量极限，当HashMap的容量达到该极限时就会进行扩容操作
	    threshold = (int) (capacity * loadFactor);
	    //初始化table数组
	    table = new Entry[capacity];
	    init();
	}



/**
*	存储实现put(key,value)
*/
public V put(K key, V value) 
{ 
 // 如果key为null，调用putForNullKey方法进行处理,保存null与table第一个位置中，这是HashMap允许为null的原因
 if (key == null) 
     return putForNullKey(value);   
 // 根据key的keyCode计算Hash值
 int hash = hash(key.hashCode()); 
 // 搜索指定hash值在对应table中的索引 
 int i = indexFor(hash, table.length);
 // 如果i索引处的Entry不为null，通过循环不断遍历e元素的下一个元素 
 for (Entry<K,V> e = table[i]; e != null; e = e.next) 
 { 
     Object k;   
     //找到指定key与需要放入的key相等（hash值相同,通过equals比较放回true）  
     if (e.hash == hash && ((k = e.key) == key || key.equals(k)))   
     {   
         V oldValue = e.value;   
         e.value = value;   
         e.recordAccess(this);   
         return oldValue;   
     }   
 } 
 // 修改次数增加1
 modCount++; 
 // 将key、value添加到i索引处
 addEntry(hash, key, value, i); 
 return null; 
}

优雅设计:新添加的Entry对象放入table数组bucketIndex索引处,而最早放入该 bucket 中的 Entry 则位于这个 Entry 链的最末端
添加位置由K-V对的Value决定
HashMap里面实现一个静态内部类Entry，其重要的属性有 key , value, next，Entry就是HashMap键值对实现的一个基础bean，我们上面说到HashMap的基础就是一个线性数组，这个数组就是Entry[]，Map里面的内容都保存在Entry[]里面。

addEntry源代码

void addEntry(int hash, K key, V value, int bucketIndex) 
{ 
    // 获取指定 bucketIndex 索引处的 Entry   
    Entry<K,V> e = table[bucketIndex];     
    // 将新创建的 Entry 放入 bucketIndex 索引处，并让新的 Entry 指向原来的 Entry   
    table[bucketIndex] = new Entry<K,V>(hash, key, value, e);   
    // 如果 Map 中的 key-value 对的数量超过了极限  
    if (size++ >= threshold)   
        // 把 table 对象的长度扩充到 2 倍。  
        resize(2 * table.length);    
}

##source##

java提高篇（二三）-----HashMap

HashMap - juedaiyuer/researchNote GitHub Wiki

⚠️ **GitHub.com Fallback** ⚠️

⚠️ GitHub.com Fallback ⚠️