Hasp Map 과 관련 된 데이터 구조

1. HashMap HashMap 사전 을 대표 하 는데 그 용량 은 자동 으로 2 의 幂 次 方 으로 조정 되 고 불 러 오 는 인 자 는 0.75 이다.HashMap 의 데이터 구 조 는 배열 + 단일 체인 표 이다.그 주간 은 배열 이 실현 되 는 것 으로 다음 과 같다.

HashMapEntry[] table;

HashMapEntry 사전 의 한 요 소 를 대표 하 는데 이것 은 하나의 체인 표 구조 로 다음 과 같이 정의 한다.

static class HashMapEntry implements Entry {
    final K key;
    V value;
    final int hash;
    HashMapEntry next; //   
}

a. HashMap 에서 데 이 터 를 읽 는 코드 는 다음 과 같다.

public V get(Object key) {
    int hash = Collections.secondaryHash(key);
    HashMapEntry[] tab = table;
    for (HashMapEntry e = tab[hash & (tab.length - 1)]; e != null; e = e.next) {
        K eKey = e.key;
        if (eKey == key || (e.hash == hash && key.equals(eKey))) {
            return e.value;
        }
    }
    return null;
}

먼저 들 어 오 는 key 대상 의 hash 값 을 계산 하고 계산 방법 은 위치 가 없 는 이동 연산 이 며 O (1) 연산 량 은 이 해시 값 이 배열 에 있 는 요소 의 위 치 를 결정 한다 고 볼 수 있 으 며 여 기 는 적당 한 위치 라 고 할 수 있다.
그 다음 에 배열 의 적당 한 위치 에서 링크 를 옮 겨 다 니 고 전송 key 대상 을 사용 하여 링크 대상 과 일치 합 니 다.일치 조건 은 두 개 입 니 다. 그 중 하 나 를 만족 시 키 면 작업 사전 에 이 키 가 저 장 된 대상 이 있 습 니 다.

key 대상 의 인용 이 같다

key 대상 의 hash 값 이 같 고 equals() 방법 도 같다.

이 는 사전 의 수치 와 덮어 쓰기 발생 여 부 는 완전히 key 대상 에 의 해 결정 되 고 value 대상 과 아무런 관계 가 없다 는 것 을 의미한다.
그 중 두 번 째 조건 은 키 대상 이 완전히 같 아야 한 다 는 뜻 으로 주의해 야 한다.때로는 key 대상 의 hash 값 은 같 지만 같 지 않다.
b. HashMap 에 데 이 터 를 기록 하 는 것 과 같은 이치

public V put(K key, V value)

먼저 K 의 해시 가 배열 에 있 는 위 치 를 계산 한 다음 에 링크 를 옮 겨 다 니 며 값 이 존재 하면 업데이트 하고 존재 하지 않 으 면 만 듭 니 다.
2. LinkedHashMap LinkedHashMap 는 HashMap 의 하위 클래스 다.HashMap 의 실현 은 그의 읽 기 가 무 작위 적 이라는 것 을 결정 했다. LinkedHashMap 은 삽입 순 서 를 강조 했다. 이 는 아직도 배열 + 링크 의 구 조 를 사용 하지만 요소 에 머리 와 꼬리 지침 을 추가 하여 더 블 링크 의 구 조 를 형성 하고 전체 데 이 터 는 전체적인 머리 지침 을 제시 했다. 그 내부 의 요 소 는 다음 과 같다.

static class LinkedEntry extends HashMapEntry {
    LinkedEntry nxt;
    LinkedEntry prv;
}

3.LruCache LruCache 캐 시 에 주로 사용 되 는데 그 기능 은 LinkedHashMap 대상 대리 에 의 해 이 루어 진다.
특이 한 점 은 LruCache 키 대상 의 메모리 크기 를 계산 하고 저장 대상 의 총 크기 를 지정 한 범위 내 에서 유지 해 야 한 다 는 것 이다.용량 을 초과 하면 LruCache 일부 데 이 터 를 조정 하고 삭제 하 며 실제로 어떤 전략 을 사용 하면 스스로 정의 할 수 있 습 니까?
또한 LruCache 읽 기와 쓰기 시 라인 이 안전 하고 빈 값 을 지원 하지 않 으 며 명중 수 등 캐 시 에 사용 되 는 통계 정 보 를 유지 합 니 다.

public class LruCache {
    private final LinkedHashMap map;

    private int size;
    private int maxSize;

    private int putCount;
    private int createCount;
    private int evictionCount;
    private int hitCount;
    private int missCount;
}

LruCache 강 한 인용 을 사용 하여 대상 에 대한 통 제 를 강화 했다.대기 열 크기 는 기본적으로 4M 입 니 다.
4.ArrayMap HashMap 는 자바 의 유 니 버 설 클래스 입 니 다. HashMap 의 약점 은 매우 많 습 니 다. 예 를 들 어 기본 유형 을 key 값 으로 지원 하지 않 으 면 포장 하여 전환 해 야 합 니 다.라인 이 안전 하지 않 음;링크 는 방문 효율 에 영향 을 주 는 등 안 드 로 이 드 util 패 키 지 는 구체 적 인 유형 에 대한 최적화 데이터 구조 체 를 많이 정의 했다.ArrayMap 완전한 배열 로 HashMap 를 개선 했다. 그 정 의 는 다음 과 같다.

int[] mHashes; //  key   hash ，             
Object[] mArray;//     
int mSize;

이 사전 의 키 값 은 대상 에 대해 하나의 배열 에 존재 하 며, key-value-key-value 형식 을 사용 하 며, key 대상 의 해시 값 은 키 값 이 맞 는 배열 의 유일한 위 치 를 결정 하지만, 계산 은 HashMap 과 다르다.
대상 을 읽 을 때 먼저 key 대상 의 해시 값 을 계산 한 다음 해시 값 배열 에서 찾 습 니 다. 존재 하면 이 값 이 사전 에 저장 되 어 있 음 을 설명 합 니 다. 해시 값 으로 배열 에 있 는 요 소 를 얻 고 대상 을 읽 을 수 있 습 니 다.
기록 대상 과 같은 이치 로 키 대상 의 해시 값 을 계산 한 다음 업데이트 하거나 만 듭 니 다.
5.SparseArray SparseArray 는 HashMap 를 한층 더 개선 한 것 으로 key 값 이 int 유형의 사전 으로 포장 체 제 를 사용 하지 않 고 불필요 한 Entry 대상 이 필요 하지 않다.즉 SparseArray 키 유형 이 int 로 고정 되 어 있 는 맞 춤 형 사전 으로 범 형 체제 의 제한 을 받 아 HashMap 은 이 점 을 실현 할 수 없다.

public class SparseArray implements Cloneable {
    private static final Object DELETED = new Object(); //    
    private boolean mGarbage = false;//         
    private int[] mKeys; //key  
    private Object[] mValues; //   
    private int mSize;
}

배열 을 읽 는 원 리 는 같 습 니 다. key 값 에 따라 요소 의 위 치 를 찾 으 면 위치 에서 값 형식 을 읽 습 니 다.그러나 이 키 값 은 int 형식 일 뿐 hash 배열 사용 을 취소 하고 위 치 를 검색 하 는 알고리즘 도 이 진 검색 으로 바 뀌 었 습 니 다.

public E get(int key, E valueIfKeyNotFound) {
    int i = ContainerHelpers.binarySearch(mKeys, mSize, key);

    if (i < 0 || mValues[i] == DELETED) {
        return valueIfKeyNotFound;
    } else {
        return (E) mValues[i];
    }
}

이 진 검색 을 통 해 검색 효율 을 높이 기 때문에 key 배열 은 순 서 를 유지 해 야 합 니 다. 이 로 인해 데 이 터 를 기록 할 때 삽입 작업 을 해 야 합 니 다. 자주 기록 하고 삭제 하면 이러한 데이터 구 조 를 사용 하면 우 위 를 잃 게 됩 니 다.
이 문 제 를 최적화 하기 위해 SparseArray 는 빈번 함 과 삭 제 를 피하 기 위해 타성 삭 제 를 사용 했다. 특정한 값 을 삭제 할 때 표시 만 하고 배열 을 정리 할 때 통일 적 으로 처리 해 야 한다.
2 분 검색 자 체 는 HashMap 의 비트 연산 보다 훨씬 느 렸 다. 또한 SparseArray 의 배열 은 비교적 큰 규모 의 데 이 터 를 저장 하기에 적합 하지 않 고 데이터 양 이 시간 (예 를 들 어 몇 백 이내) 에 만 적합 하 며 차이 가 현저 하지 않 은 상황 에서 만 사용 할 수 있다 는 것 을 결정 했다.
7. 기타 데이터 구조
7.1 유리수 (Rational)

Rational rational = Rational.parseRational("1/2");
rational = Rational.parseRational("1:2");

7.2 너비 / 높이 (사이즈 / 사이즈 F)

Size size = new Size(100,100);
size = Size.parseSize("100*100");

7.3 두 원소 원 그룹 (Pair)

Pair apple = new Pair<>("apple",1);
Pair android = Pair.create("android",2);

7.4 범위 (범위)
두 값 사이 의 범 위 를 설명 하고 값 대상 이 Comparable 인 터 페 이 스 를 실현 하기 만 하면 됩 니 다.상하 한, 교 집합, 확장, claim 등의 동작 을 지원 합 니 다.

Range range = Range.create(1,20);

참고 문헌

android.util

Jenkins hash function