Hashmap은 또한 우리가 많이 사용하는 컬렉션입니다. 해시 테이블을 기반으로 한 맵 인터페이스의 구현이며 키 값 형태로 존재합니다. 해시 맵에서 키 값은 항상 전체적으로 처리됩니다. 시스템은 해시 알고리즘을 기반으로 키 값의 저장 위치를 계산합니다. 키를 통해 항상 값을 신속하게 저장하고 검색 할 수 있습니다. 해시 맵에 대한 액세스를 분석하겠습니다.
1. 정의
해시 맵은 맵 인터페이스를 구현하고 AbstractMap을 상속합니다. 맵 인터페이스는 값에 대한 키 매핑 규칙을 정의하고 AbstractMap 클래스는이 인터페이스를 구현하는 데 필요한 작업을 최소화하기 위해 MAP 인터페이스의 백본 구현을 제공합니다. 실제로 AbstractMap 클래스는 MAP를 구현했습니다. 여기에지도 lz를 표시하는 것이 더 명확해야한다고 생각합니다!
공개 클래스 해시 맵 <k, v> 확장 actractmap <k, v> 구현 <k, v>, 클로닝 가능, 직렬화 가능
2. 생성자 함수
Hashmap은 세 가지 생성자를 제공합니다.
hashmap () : 기본 초기 용량 (16)과 기본 하중 계수 (0.75)가있는 빈 해시 맵을 구성합니다.
HASHMAP (Int InitialCapacity) : 지정된 초기 용량 및 기본 하중 계수 (0.75)가있는 빈 해시 맵을 구성합니다.
HASHMAP (Int InitialCapacity, Float Loadfactor) : 지정된 초기 용량 및 하중 계수로 빈 해시 맵을 구성합니다.
여기에는 초기 용량, 로딩 계수의 두 매개 변수가 언급되어 있습니다. 이 두 매개 변수는 해시 맵의 성능에 영향을 미치는 중요한 매개 변수입니다. 용량은 해시 테이블의 버킷 수를 나타냅니다. 초기 용량은 해시 테이블을 만들 때의 용량입니다. 로딩 계수는 용량이 자동으로 증가하기 전에 해시 테이블에 도달 할 수있는 스케일입니다. 해시 테이블 공간의 사용 정도를 측정합니다. 하중 계수가 클수록 해시 테이블의 하중 정도가 높고 그 반대도 마찬가지입니다. 링크 된 목록 방법을 사용하는 해시 테이블의 경우 요소를 찾는 평균 시간은 O (1+A)입니다. 따라서 하중 계수가 더 크면 공간이 더 완전히 활용되지만 결과는 검색 효율의 감소입니다. 하중 계수가 너무 작 으면 해시 테이블의 데이터가 너무 드물어 공간에 심각한 폐기물이 발생합니다. 시스템의 기본 부하 계수는 0.75이며 일반적으로 수정할 필요가 없습니다.
Hashmap은 빠른 액세스를 지원하는 데이터 구조입니다. 성능을 이해하려면 데이터 구조를 이해해야합니다.
III. 데이터 구조
Java에서 가장 일반적으로 사용되는 두 가지 구조는 배열 및 시뮬레이션 포인터 (참조)임을 알고 있습니다. 거의 모든 데이터 구조는이 두 가지와 함께 구현 될 수 있으며 해시 맵에 대해서도 마찬가지입니다. 실제로 해시 맵은 데이터 구조와 같이 "링크 된 목록 해시"입니다.
위의 그림에서 Hashmap의 기본 구현이 배열인지 또는 어레이의 모든 항목이 체인인지 확인할 수 있습니다. 매개 변수 초기 범위는 배열의 길이를 나타냅니다. 다음은 해시 맵 생성자의 소스 코드입니다.
public hashmap (int initialcapacity, float loadfactor) {// 초기 용량은 <0이 될 수 없습니다. // 초기 용량> 최대 용량 값, 해시 맵의 최대 용량은 2^30 if (initialCapacity> maximum_capacity) 초기 커피 = maximum_capacity; //로드 계수가 <0이 될 수 없습니다. // 초기 범위보다 가장 작은 2의 N- 힘 값을 계산합니다. int 용량 = 1; while (용량 <초기 범위) 용량 << = 1; this.loadfactor = loadfactor; // 해시 맵의 용량 제한을 설정합니다. 해시 맵의 용량 이이 한계에 도달하면 용량 확장 작업은 임계 값 = (int) (용량 * loadfactor); // 테이블 배열 초기화 테이블 = 새 항목 [용량]; init (); } 소스 코드에서 볼 수 있듯이 새 해시 맵이 생성 될 때마다 테이블 배열이 초기화됩니다. 테이블 배열의 요소는 입력 노드입니다.
정적 클래스 항목 <k, v>는 map.entry <k, v> {최종 K 키; v 값; 입력 <k, v> 다음; 최종 int 해시; /*** 새 항목을 만듭니다. */ Entry (int h, k k, v v, enter <k, v> n) {value = v; 다음 = n; 키 = k; 해시 = h; } .....}그중에는 항목이 내부 클래스의 해시 맵 (Hashmap)이 있으며, 여기에는 키 키, 값 값, 다음 노드 및 해시 값이 포함되어 있습니다. 이것은 매우 중요합니다. 항목이 링크 된 목록으로 테이블 배열의 항목을 형성하기 때문입니다.
위의 내용은 해시 맵의 데이터 구조를 간단히 분석하고 아래는 해시 맵이 빠른 액세스를 구현하는 방법을 탐색합니다.
4. 스토리지 구현 : put (키, VLAUE)
먼저 소스 코드를 살펴 보겠습니다
public v put (k key, v value) {// 키가 null 일 때 putfornullkey 메서드를 호출하여 null과 테이블의 첫 번째 위치를 저장하십시오. 이것이 해시 맵이 null if (key == null) return putfornullkey (value)를 허용하는 이유입니다. // 키의 해시 값을 계산 int hash = hash (key.hashcode ()); ----- (1) // 테이블 배열에서 키 해시 값의 위치를 계산 int i = indexfor (Hash, table.length); ----- (2) // i에서 반복하고 키가 저장된 위치를 찾으십시오 (Entry <k, v> e = 테이블 [i]; e! = null; e = e.next) {object k; // 체인에 동일한 해시 값이 있는지 판단하십시오 (키는 동일합니다) // 동일하게 존재하는 경우 값을 직접 덮어 내고 (e.hash == hash && ((k = e.key) == 키 || key.equals (k))) {v oldValue = a.value; // 이전 값 = 새 값 e.Value = value; e.recordaccess (this); OldValue를 반환하십시오. // end value를 반환}} // 1 modcount ++ 씩 수정 수를 늘리십시오. // i 위치에 키와 값을 추가합니다 addentry (해시, 키, 값, i); 널 리턴; }소스 코드를 통해 해시 맵 저장 데이터의 프로세스는 다음과 같습니다. 먼저 키가 null인지 결정합니다. NULL 인 경우 PutFornullkey 메소드를 직접 호출하십시오. 비어 있지 않은 경우 먼저 키의 해시 값을 계산 한 다음 해시 값에 따라 테이블 배열의 인덱스 위치를 검색하십시오. 이 위치에 요소가 있으면 동일한 키가 존재하는지 비교하십시오. 존재하는 경우 원래 키의 값을 덮어 쓰고, 그렇지 않으면 체인 헤드의 요소를 저장하십시오 (저장된 첫 번째 요소는 체인 끝에 배치됩니다). 테이블에 요소가 없으면 직접 저장됩니다. 이 과정은 간단 해 보이지만 실제로 내부 정보가 있습니다. 다음과 같이 몇 가지 사항이 있습니다.
1. 먼저 반복을 봅시다. 여기서 반복의 이유는 동일한 키 값의 존재를 방지하기 때문입니다. 두 개의 해시 값 (키)이 동일하다는 것이 발견되면 해시 맵의 처리 방법은 이전 값을 새 값으로 바꾸는 것입니다. 키는 여기서 처리되지 않으며 해시 맵에는 두 개의 동일한 키가 없다고 설명합니다.
2.보기 (1)과 (2). 이것이 해시 맵의 본질입니다. 우선, 순수한 수학적 계산 인 해시 방법이 있으며, 이는 H의 해시 값을 계산하는 것입니다.
정적 int 해시 (int h) {h ^ = (h >>> 20) ^ (h >>> 12); h ^ (h >>> 7) ^ (h >>> 4); }해시 맵 테이블의 경우 데이터 배포가 고도 있어야한다는 것을 알고 있습니다 (각 항목에 대해 하나의 요소 만 있으면 직접 찾을 수 있습니다). 너무 빡빡하거나 느슨 할 수 없습니다. 너무 빡빡하면 쿼리 속도가 느리면 너무 느슨하면 공간이 낭비됩니다. 해시 값을 계산 한 후에 테이블 요소가 동일하게 분포되도록하려면 어떻게해야합니까? 우리는 곰팡이 획득을 생각하지만 금형 획득이 많이 소비되기 때문에 해시 맵은 다음과 같이 처리합니다. 인덱스 용 메소드를 호출하십시오.
static int Indexfor (int h, int length) {return h & (longth-1); }해시 맵의 기본 배열의 길이는 항상 2의 N- 전원에 있으며 생성자에 존재합니다 : 용량 << = 1; 그렇게하는 것은 항상 해시 맵의 기본 배열의 길이가 2의 N- 전력에 있는지 확인할 수 있습니다. 길이는 n 전력이 2의 전원이되면 H & (길이 -1)는 길이의 계수를 취하는 것과 동일하며, 속도는 모듈러스를 직접 복용하는 것보다 훨씬 빠릅니다. 이것은 속도 측면에서 해시 맵의 최적화입니다. 그것이 왜 Nth Power에 2인지에 관해서는 다음과 같은 설명입니다.
H & (길이 -1)가 하나만있는 Indexfor 메소드로 돌아가 봅시다. 위의 계수 작업 외에도이 문장에는 매우 중요한 책임도 있습니다. 테이블 데이터를 균등하게 배포하고 공간을 최대한 활용하십시오.
여기서 우리는 길이가 16 (2^n)과 15이고 h는 5, 6 및 7이라고 가정합니다.
n = 15 인 경우 6과 7의 결과는 동일합니다. 즉, 테이블에 저장된 위치가 동일하며, 즉 충돌이 발생하고 6과 7은 한 위치에서 링크 된 목록을 형성하여 쿼리 속도가 줄어 듭니다. 여기서는 3 개의 숫자 만 분석되지만 많지는 않으므로 0-15를 살펴 보겠습니다.
위의 차트에서 우리는 총 8 개의 충돌이 보이고 동시에 낭비 된 공간이 매우 크며, 1, 3, 5, 7, 9, 11, 13, 13, 13, 13, 즉 데이터가 저장되지 않은 것으로 나타났습니다. 14로 수행 및 작동 할 때, 마지막 결과의 마지막 비트는 항상 0이 될 것이기 때문에, 즉 0001, 0011, 0101, 0111, 1001, 1011, 1101, 1111 및 1111의 위치에 데이터를 저장하는 것은 불가능하기 때문입니다. 공간이 줄어들고 충돌 가능성이 더욱 증가하여 느린 query 속도로 이어질 것입니다. 길이 = 16 인 경우 길이 1 = 15는 1111입니다. 그런 다음 낮은 비트 및 작동을 수행 할 때는 값이 항상 원래 해시 값과 동일하며 고 비트 작동을 수행 할 때는 값이 저 비트 값과 같습니다. 따라서 길이 = 2^n이면 상이한 해시 값 사이의 충돌 확률이 비교적 작으므로, 이는 데이터가 테이블 배열에 고르게 분포되고 쿼리 속도가 더 빠릅니다.
여기서 우리는 Put Process를 검토합니다. 해시 맵에 키 값 한 쌍을 추가하려면 시스템이 먼저 키의 해시 값을 계산 한 다음 해시 값에 따라 테이블에 저장된 위치를 확인합니다. 이 위치에 요소가 없으면 직접 삽입하십시오. 그렇지 않으면, 그 시점에서 요소 목록을 반복하고 그에 따라 키의 해시 값을 비교하십시오. 두 해시 값이 동일하고 키 값이 동일하면 (E.Hash == HASH && ((k = E.Key) == key || key.equals (k))), 원래 노드의 값은 새 항목의 값으로 덮어 씁니다. 두 해시 값이 같지만 키 값이 같지 않으면 노드를 연결된 목록의 헤더에 삽입하십시오. 특정 구현 프로세스는 다음과 같이 Addentry 메소드를 참조하십시오.
void addentry (int hash, k key, v value, int buctIndex) {// 입력 입력 <k, v> e = 테이블 [buctIndex]; // 새로 생성 된 항목을 BucketIndex 인덱스에 넣고 새 입력 지점을 원래 입력 테이블 [buctIndex] = 새 항목 <k, v> (해시, 키, 값, e); // 해시 맵의 요소 수가 한계를 초과하면 용량이 IF (size ++> = threshold) resize (2 * table.length)보다 두 배입니다. }이 방법에는 두 가지 점이 있습니다.
하나는 체인의 생성입니다. 이것은 매우 우아한 디자인입니다. 이 시스템은 항상 BucketIndex에 새 항목 객체를 추가합니다. BucketIndex에 객체가있는 경우 새로 추가 된 항목 객체가 원래 항목 객체를 가리켜 입력 체인을 형성합니다. 그러나 BucketIndex에 항목 객체가 없으면 E == NULL이면 새로 추가 된 입력 객체가 NULL을 가리키며 입구 체인이 생성되지 않습니다.
2. 용량 확장.
해시 맵의 요소 수가 증가함에 따라 충돌 가능성이 커지고 생성 된 링크 목록의 길이가 더 길어지고 길어집니다. 이것은 필연적으로 해시 맵의 속도에 영향을 미칩니다. 해시 맵의 효율성을 보장하기 위해 시스템은 특정 중요한 지점에서 용량을 확장해야합니다. 이 중요한 점은 해시 맵의 요소 수가 테이블 배열 길이* 하중 계수와 같을 때입니다. 그러나 스케일링은 새로운 테이블 배열 에서이 데이터의 위치를 재 계산하고 복사해야하기 때문에 매우 시간이 많이 걸리는 프로세스입니다. 따라서 해시 맵의 요소 수를 예측 한 경우 사전 설정 요소의 수는 해시 맵의 성능을 효과적으로 향상시킬 수 있습니다.
5. 읽기 구현 : get (키)
해시 맵의 저장과 비교할 때 철수는 비교적 간단합니다. 키의 해시 값을 통해 테이블 배열의 인덱스에서 항목을 찾은 다음 키에 해당하는 값을 반환하십시오.
public v get (Object Key) {// null 인 경우 getfornullkey 메서드를 호출하여 해당 값을 반환합니다 (key == null) retudfornullkey (); // 키 int Hash = hash의 해시 코드 값을 기준으로 해시 코드를 계산합니다 (key.hashcode ()); // (Entry <k, v> e = 테이블 [indexfor (hash, table.length)]; e! = null; e = e.next) {object k; // 검색 된 키가 검색 된 키와 동일하면 (e.hash == hash && ((k = e.key) == key || key.equals (k))) return e.value; } return null; } 여기서는 키를 기반으로 신속하게 검색 할 수있는 값은 해시 맵의 데이터 구조와 분리 할 수 없을뿐만 아니라 항목과 관련이 있습니다. 앞에서 언급했듯이 Hashmap은 저장된 절차에 키와 값을 별도로 저장하지 않지만 입력 객체 인 전체 키 값으로 처리됩니다. 동시에 값은 키의 첨부 파일과 동일합니다. 스토리지 프로세스 중에 시스템은 키의 해시 코드를 기반으로 테이블 어레이의 항목의 저장 위치를 결정하고 페치 과정에서 해당 항목 객체도 키의 해시 코드에 따라 꺼집니다.
원본 링크 : http://www.cnblogs.com/chenssy/p/3521565.html
위는이 기사의 모든 내용입니다. 모든 사람의 학습에 도움이되기를 바랍니다. 모든 사람이 wulin.com을 더 지원하기를 바랍니다.