Map 인터페이스, HashMap 소스 코드 상세 설명

1. 맵 인터페이스
집합 프레임 워 크 맵 을 보면 Map 은 collection 의 하위 인터페이스 로 key - value 키 가 맞 는 형식 으로 데 이 터 를 저장 합 니 다.

데이터 구조: 해시 표

해시 표: 키 코드 를 통 해 하나의 값 의 데이터 구조

를 나타 낸다.

해시 함수: 키 와 값 맵 의 맵 관계 (해시 함수 의 구체 적 인 방법 (9 번 째)

2. HashMap
1. 특징:

               
              ，     
		     null

2. 상용 방법 소개
put（key，value）；//삽입 키 - 값 쌍 int size();//map 에 키 쌍 의 개 수 를 저장 합 니 다 get（Object key）；//키 를 통 해 값 찾기 boolean isEmpty () / / 판정 공 boolean contains Value (Object value) / / 값 이 존재 하 는 지 판단 하기 boolean containsKey (Object key) / / 키 가 존재 하 는 지 판단 하기 remove (Object key) / / 키 를 통 해 키 쌍 을 삭제 합 니 다. 3. hashMap 집합 에 대한 옮 겨 다 니 기 (세 가지 방식)

키 값 을 통 해 옮 겨 다 니 기: hashMap 인 스 턴 스 를 set 인 스 턴 스 로 전환 합 니 다 (유형 은 map. entry < >),

 Iterator<Map.Entry<String,String>> iterator = hashMap.entrySet().iterator();
      while(iterator.hasNext()){
		 Map.Entry<String,String> next = iterator.next();
		 String  key = next.getKey();
		 String value = next.getValue();
		 System.out.print(key+":"+value+".");
					 }

키 를 통 해 옮 겨 다 니 기 (hashMap. keyset (). iterator ()

Iterator<String> iterator1 = hashMap.keySet().iterator();
		while(iterator1.hasNext()){
		 String next = iterator1.next();
		 System.out.print(next+".");
					 }

값 으로 옮 겨 다 니 기 (hashMap. values (). iterator ()

Iterator<String> iterator2 = hashMap.values().iterator();
	 while(iterator2.hasNext()){
	 String next = iterator2.next();
	 System.out.print(next+" ");
						}

4. JDK 1.7 소스 코드 분석

계승 관 계 는 AbstractMap (jdk 1.2 시작) 을 계승 하여 Map 인 터 페 이 스 를 실현 하여 복제 할 수 있 고 직렬 화 할 수 있다

.

public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>,
 Cloneable, Serializable

바 텀 데이터 구조 배열 + 링크 [배열 에 저 장 된 것 은 하나의 entry 실체 이 고 hash 에서 같은 색인 위치 에 있 는 데 이 터 는 링크 를 통 해 연 결 됩 니 다]

기본 속성 과 기본 값

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
              16

static final int MAXIMUM_CAPACITY = 1 << 30;
           

static final float DEFAULT_LOAD_FACTOR = 0.75f;
       -》      

static final Entry<?,?>[] EMPTY_TABLE = {};

transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;

static class Entry<K,V>{
  
 final K key; //    key（ ）
   
V value;   //    value（ ）
   
Entry<K,V> next;  //next  

int hash;  // key   hash

구조 함수:

  1。      、      
 public HashMap(int initialCapacity, float loadFactor) {
  //      
  if (initialCapacity < 0)
	  throw new IllegalArgumentException("Illegal initial capacity: " +
										 initialCapacity);
  if (initialCapacity > MAXIMUM_CAPACITY)
	  initialCapacity = MAXIMUM_CAPACITY;
  if (loadFactor <= 0 || Float.isNaN(loadFactor))
	  throw new IllegalArgumentException("Illegal load factor: " +
										 loadFactor);
  //    、       
  this.loadFactor = loadFactor;
  threshold = initialCapacity;
  init();
}

   2。               
	public HashMap(int initialCapacity) {
		this(initialCapacity, DEFAULT_LOAD_FACTOR);
	}
   3。             
	public HashMap() {
		this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
	}

   4。  map          
	public HashMap(Map<? extends K, ? extends V> m) {
		this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
					  DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);
		inflateTable(threshold);

		putAllForCreate(m);
	} 	 

성장 방식: (확장 방식) 2 배 확장 ① 확장 시기: 현재 저장 요소 의 개수 size > = 확장 한도 값 threshold 시 확장 (threshold = 현재 배열 용량 * 로드 인자) ② 확장 크기: 2 배의 배열 크기 table. length (배열 이 2 의 지수 급 관 계 를 만족 시 켜 야 함)

//              
         table  ，              ，            
 void resize(int newCapacity) {
        Entry[] oldTable = table; 
        int oldCapacity = oldTable.length;
        if (oldCapacity == MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return;
        }
        Entry[] newTable = new Entry[newCapacity];//      table  
        transfer(newTable, initHashSeedAsNeeded(newCapacity));
        table = newTable;
     threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
    }
// transfer  ：(   CPU   100％)
 void transfer(Entry[] newTable, boolean rehash) {
	      int newCapacity = newTable.length;
	      for (Entry<K,V> e : table) {
		    while(null != e) {
			Entry<K,V> next = e.next;
			if (rehash) {
				e.hash = null == e.key ? 0 : hash(e.key);
			}
			int i = indexFor(e.hash, newCapacity);
			e.next = newTable[i];
			newTable[i] = e;
			e = next;

//     ，                   
void createEntry(int hash, K key, V value, int bucketIndex) {
	      Entry<K,V> e = table[bucketIndex];
	      table[bucketIndex] = new Entry<>(hash, key, value, e);
	      size++;}    
    

상용 방법 연구: 1. put () 방법 연구 * * * * * * HashMap 의 작업 원리!!!!원본 코드 분석: 첫 번 째 요 소 를 삽입 하려 면 배열 을 초기 화해 야 합 니 다. 배열 길이 가 2 인 지수 입 니 다. key 가 null 또는 비 null 이 key 가 null 이 아 닐 때 key 해시 (hashing) 를 통 해 데이터 가 존재 하 는 색인 위 치 를 찾 고 이 위치 에 있 는 링크 를 옮 겨 다 니 며 (key 가 존재 하 는 지 판단 하면 value 를 교체 하고 새로운 entry 를 만 드 는 것 이 존재 하지 않 습 니 다) key 가 null 일 때배열 의 색인 이 0 인 위치 가 존재 합 니 다. 이 위치 에 있 는 링크 를 옮 겨 다 니 며 key 가 null 인 노드 가 존재 하 는 지 확인 합 니 다. 존재 하면 value 의 값 을 들 어 오 는 value 로 업데이트 합 니 다. 이 링크 에 key 가 null 인 노드 가 저장 되 지 않 으 면 새로운 entry 노드 를 만들어 이 링크 를 삽입 합 니 다!

 public V put(K key, V value) {
        if (table == EMPTY_TABLE) {
            inflateTable(threshold);
        }
        if (key == null)  //key null
            return putForNullKey(value);
        //key  null
        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;
    }

//key null ：
 private V putForNullKey(V value) {
        for (Entry<K,V> e = table[0]; e != null; e = e.next) {
            if (e.key == null) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }
        modCount++;
        addEntry(0, null, value, 0);
        return null;
    }

get () 방법 연구: 소스 코드 분석: 키 키 를 통 해 value ① 키 가 null 인지 아 닌 지 를 판단 하 는 특수 처리 입 니 다. 0 번 색인 위치 에서 요 소 를 직접 찾 습 니 다 ② 키! =null 시, 먼저 하 쉬 를 통 해 색인 위 치 를 찾 고, 색인 위 치 를 통 해 현재 링크 를 찾 고, 키 를 옮 겨 다 니 며 키 가 같은 지 판단 하여 value 를 찾 아 되 돌려 줍 니 다

   public V get(Object key) {
        if (key == null)
            return getForNullKey();
        Entry<K,V> entry = getEntry(key);
        return null == entry ? null : entry.getValue();
    }