산 목록 원리, HashMap 소스 코드 분석

1. HashSet 의 실현 원리 HashMap 은 중복 되 는 요소 (소스 코드 명중 후 return) 를 추가 하지 않 습 니 다. 또한 HashSet 바 텀 은 HashMap 을 바탕 으로 이 루어 지기 때문에 Set 의 add 방법 은 중복 되 는 요 소 를 추가 할 수 없습니다.요약: 바 텀 은 HashMap 을 바탕 으로 이 루어 집 니 다. 구체 적 인 코드 는 다음 과 같 습 니 다.

    HashSet(int initialCapacity, float loadFactor, boolean dummy) {
        map = new LinkedHashMap<E,Object>(initialCapacity, loadFactor);
    }
    public boolean add(E e) {
        return map.put(e, PRESENT)==null;
    }    

HashSet 의 add 방법 은 Map 의 put 방법 으로 이 루어 집 니 다.put 명중 업데이트 값 을 찾 고 이전 값, 이전 값 을 되 돌려 줍 니 다! =null, 존재 하 는 요소 add 방법 을 추가 하여 false 로 되 돌려 줍 니 다.put 가 명중 하지 않 으 면 null 을 직접 삽입 하고 되 돌려 줍 니 다. null = = null 이기 때문에 add 는 true 를 되 돌려 줍 니 다.기본 값 present 를 저장 합 니 다.
2. HashMap 의 실현 원리

HashMap put 소스 코드 - 단판

public V put(K key, V value) {
    for( Node x = first[ key.hashcode() % M ]; x!=null; x = x.next){
     if(x.key == key){
     	V oldValue = x.value;
     	x.value = value; 
     	return oldValue; //    
     }
    }
    first[ key.hashcode() % M ] = new Node(key, value，first); //   
    return null;

산 목록 은 링크 배열 을 사용 하여 이 루어 집 니 다. 각 목록 은 통 이 라 고 합 니 다.먼저 hashCode () 를 계산 한 다음 에 통 의 총수 와 나머지 를 취하 면 얻 은 결 과 는 배열 의 색인 (통 의 색인) 이다.때로는 통 이 가득 차 면 산열 충돌 이 일어난다.해시 충돌 을 해결 하 는 것 은 지퍼 법 이나 선형 탐색 법 일 수 있다.통 은 사실 지퍼 법.선형 탐색 법 은 개방 주소 법 이 라 고도 부 르 는데 주소 에 따라 충돌 하 는 다음 빈자리 에 삽입 하 는 것 이다.
3. List, Set 와 Map 의 차이 점 을 기억 하 는 김 에 List, Set 와 Map 의 차이 점 을 기억 해 보 세 요.

Collection 은 add 이 고 Map 은 put 입 니 다.

List 는 질서 있 는 집합 으로 요 소 는 용기 의 특정한 위치 에 증가 하고 교체 기 를 사용 하여 요 소 를 추가 하 는 것 은 실제 적 인 의미 가 있 으 며 Set 와 Map 은 무질서 하 다.

4. ConcurrentHashMap 은 스 레 드 안전 자바 7 전에 세그먼트 잠 금 을 통 해 이 루어 집 니 다.자바 8 노드 로 구현;
5. 알고리즘 문제 에서 HashMap 의 사용

leetcode 는 두 수의 합 target

을 실현 합 니 다.

HashMap<Integer, Integer> map = new HashMap();
int n = nums.length;
for(int i=0; i<n; i++){
   if(map.containsKey(target-nums[i])){
       int result[] = new int[2];
       result[0] = map.get(target-nums[i]);
       result[1] = i;
       return result;
   }
    else
        map.put(nums[i], i);
}
return null;