리코드 요약explore card.

organizes data using hash functions in order to support quick insertion and search

두 가지 유형이 다릅니다.

산열 세트
데이터 구조 설정 - 중복 값이 없습니다.

분산 매핑
지도 데이터 구조 - 저장(키, 값) 쌍

해시 함수

maps a big number or string to a small integer that can be used as index in hash table.

콘셉트

개념here과 forjava specific info를 한층 더 읽다

부하 계수

number of of elements stored in table / number of buckets

average number of key-value pairs per bucket.

It offers tradeoff between time and space complexity

JavaHashmap의 부하 계수는 0.75이다.

용량/초기 용량

number of bucketsJavaHashMap의 초기 용량16

문턱

Current Capacity * Load Factor

Capacity of Hashmap is doubled each time it reaches threshold

자바에서 Hashmap의 초기 용량은 16이고 부하 계수는 0.75이다.따라서 임계값은 16 * 0.75 = 12입니다.
따라서 해시맵에 12번째 요소를 추가하면 해시맵의 용량은 16에서 32로 증가한다.

다시 카드를 씻는다

Hashing again. (eg. when capacity is increased)

새 용량의 새 HashMap 객체를 만들면 모든 이전 요소(키 값 쌍)가 해시 코드를 다시 계산한 후 새 객체에 배치됩니다.
초기 용량과 부하 계수의 선택은 재회화 작업의 횟수를 최소화해야 한다.
예.
부하 계수는 1.0f이다.(현재 용량의 100%를 채운 후 재회색)

공간 절약

기존 요소

의 검색 시간 증가
하중 계수는 0.5f이다.

현재 용량이 50%가 되면 다시 회색으로 돌아갑니다.

재회색화 작업의 수를 증가시킵니다.

해시표

use hash function to map keys to buckets

새 열쇠 삽입

산열 함수는 어느 통 키를 분배할지 결정합니다

키는 해당 통에 저장

검색 키

해시표는 해시 함수를 사용하여 버킷을 찾습니다

통에서 열쇠 검색

예를 들어 y = x % 5는 산열 함수이다
1987년과 2년은 같은 통이었다.(통2)
해시 함수를 사용하여 버킷 2의 키를 검색합니다.
두 가지 기본 작업

삽입부

검색

디자인 해시표

1. 해싱 함수

assign key to bucket as uniformly as possible

이상적인 상황에서 키와 버킷은 일대일로 비치는 것이다.그러나 amount of buckets와 capacity of buckets 사이에는 항상 균형이 있다.
좋은 해싱 함수는 다음과 같아야 합니다.

효율적인 컴퓨팅

통합 배포 키

2. 충돌 감소

collision is when > 1 key is assigned to 1 bucket

이상적인 상황에서, 해시 함수는 키와 통의 일대일 반사이다.
고려 요소

버킷의 값을 어떻게 구성합니까?

스토리지 통에 너무 많은 할당 값은 무엇입니까?

어떻게 버킷에서 목표치를 검색합니까?

고려해야 할 사항:

삽 용량

동일한 스토리지 통에 매핑될 수 있는 키 수

주어진 열쇠 수 N

N: 작지만 일정한 -->array 스토리지 키O(N)

N: 변수/크기 -->height balanced binary search tree 스토리지 키용O(log(n))

충돌 처리

situation where newly inserted key maps to an already occupied slot in hash table.

해시 함수는 큰 정수나 문자열의 키로 작은 숫자를 만들기 때문이다.두 키가 같은 값을 낼 수 있습니다.(예를 들어 생일 패러다임은 23명이 있어야 50%가 같은 생일을 공유할 수 있다)

1. 개별 링크

each cell of hash table point to a linked list of records that have same hash function value.

테이블 밖의 추가 메모리가 필요합니다.

개별 링크용 데이터 구조

체인 시계

ArrayList

트리

개별 링크 - 복잡성

복잡성은 독립 링크를 지원하는 하부 데이터 구조의 복잡성에 달려 있다

보통이었어

평균값은 균등한 산열로 가정한다
자세한 내용here

lf = load factor
n = number of elements
m = number of buckets

α = n / m

성공하지 못했어

O(α)성공하지 못한 검색은 단독 링크의 체인 테이블을 철저히 검색해야 합니다.균등 산열 중 체인 테이블의 평균 길이는 부하 인자이다

성공적

O(1+(α/2))검색에 성공하면 체인 테이블에 목표 키가 포함되어 있을 것입니다.평균적으로 목표 키는 체인 테이블의 앞부분에서 찾을 수 있다.

최악이었어

O(N)

최고이었어

O(1)

2. 공개 주소 찾기

all elements stored in the hash table itself.

모든 요소가 해시 테이블에 저장되어 있기 때문에, 테이블의 어떤 크기도 키의 총수보다 커야 한다.
각 테이블 항목에는 레코드 또는 NIL이 있습니다.요소를 검색하려면 테이블 슬롯을 하나씩 확인합니다.
삽입(k)
빈 슬롯을 찾고 키를 삽입할 때까지 계속 탐색하십시오
검색 (k)
플러그에 도달할 때까지 키 ==k 또는 빈 플러그를 계속 탐지합니다.
삭제(k)
키를 간단하게 삭제하면 검색에 실패할 수 있습니다.
삭제된 열쇠 슬롯은 특별히 '삭제됨' 으로 표시됩니다.항목은 삭제된 슬롯에 삽입할 수 있지만 삭제된 위치에서 검색을 중지할 수는 없습니다.

오픈 주소 지정 - 구현

1. 선형 탐지

probe for the next spot

If slot hash(x) % S is full, then we try (hash(x) + 1) % S
If (hash(x) + 1) % S is also full, then we try (hash(x) + 2) % S
If (hash(x) + 2) % S is also full, then we try (hash(x) + 3) % S 

문제 - 주요 분류 문제

tendency for a collision resolution scheme to create long runs of filled slots near the hash position of keys.

점용된 세포 덩어리는 형성할 수 있다.집단이 더 커지고hashmap의 성능을 떨어뜨릴 수 있습니다.(전체 그룹을 옮겨다녀야 값을 찾을 수 있습니다)

2. 2차 탐지

Look for the next i²th slot in the ith iteration

If slot hash(x) % S is full, then we try (hash(x) + 1*1) % S
If (hash(x) + 1*1) % S is also full, then we try (hash(x) + 2*2) % S
If (hash(x) + 2*2) % S is also full, then we try (hash(x) + 3*3) % S

문제-이차 클러스터

tendency to create long runs of filled slots away from hash position of keys

여전히 메인 그룹보다 효율적이다.그것의 목적은 초급 세포단을 분열시켜 더욱 광범위하게 분리된 세포를 탐지하는 것이다.
주요와 부차적인 분류here를 더욱 상세하게 설명하였다.

3. 이중 산열

Use another hash function hash2(x) and look for i*hash2(x) slot in i^th rotation.

If slot hash(x) % S is full, then we try (hash(x) + 1*hash2(x)) % S
If (hash(x) + 1*hash2(x)) % S is also full, then we try (hash(x) + 2*hash2(x)) % S
If (hash(x) + 2*hash2(x)) % S is also full, then we try (hash(x) + 3*hash2(x)) % S

요구 사항

두 번째 해시 함수의 계산 결과는 영원히 0이 될 수 없다

모든 배터리를 탐지할 수 있는지 확인

오픈 주소 지정 - 복잡성

자세한 내용here

m = Number of slots in the hash table
n = Number of keys to be inserted in the hash table

Load factor α = n/m  ( < 1 )

평균 - 실패

평균 분석 가설 균일 산열
검색 실패: O(1/(1 - α))삽입: O(1/(1-α))파생

probability of successful search = p

Probability 1st probe successful  = (m-n)/m = 1-α
Probability 2nd probe successful = (m-n)/(m-1) > 1-α

따라서 모든 탐지기에서 확률은 적어도 1-α이다.따라서 최악의 경우 검색에 성공하지 못할 경우 최저 실행 수량1/p = 1/(1-α)이 예상됩니다.

평균 성공률

O((1/α) * log (1/(1-α))

모범 사례

O(1)

최악의 경우

O(N)

오픈 주소 지정 및 링크

오픈 주소 지정: 캐시 성능 향상
링크:함수에 민감하지 않음

해시집

Hashset은 set 데이터 구조의 실현이다.set 데이터 패브릭에 중복된 값이 저장되지 않음

no repeated values

백그라운드에서 Hashset은 자바 HashMap에서 지원하고 자바 HashMap은 모든 키를 single constant object 에 비추기

전형적인 용법

check if value has appeared or not.

Set<Type> hashset = new HashSet<>();
for (Type key: keys) {
  if (hashset.contains(key)) {
    // there is duplicate in set
    return true;
  }
  // no duplicat add key
  hashset.add(key);
}

해시표

hash functions are used to link key and values

map 저장 데이터의 (key,value) 데이터 구조에 대한 실현

build mapping relation between key & information

사용자가 키보다 더 많은 정보를 필요로 할 때 사용합니다.

엔진 덮개

내부에서, 그것은 하나의 저장통을 유지한다.
배치(키, 값)/가져오기(키)
키 대상의

hascode () 방법을 호출해서 버킷 인덱스를 찾습니다.

hashcode()>통 수가 있으면 공식index = hashCode(key) & (n-1).을 사용하여 한 수로 변환합니다<=통 수
비트별 AND 연산자를 사용하기 때문에 해시 코드의 낮은 비트만 고려합니다.

충돌 해결

Java HashMap resolves collisions uses separate chaining (LinkedList)

키 대상의 해시 코드가 계산되면버킷의 체인 테이블을 옮겨다니며 값을 찾거나 체인 테이블의 끝에 놓으십시오.
더욱 상세한 읽기 자료는 GeeksforGeeks에서 찾을 수 있다(점차적인 과정/사례 연구 포함)보다 간략한 요약: DZone 및 javarevisited.

사용법

// 1. initialize a hash map
Map<Integer, Integer> hashmap = new HashMap<>();
// 2. insert a new (key, value) pair
hashmap.putIfAbsent(0, 0);
hashmap.putIfAbsent(2, 3);
// 3. insert a new (key, value) pair or update the value of existed key
hashmap.put(1, 1);
hashmap.put(1, 2);
// 4. get the value of specific key
System.out.println("The value of key 1 is: " + hashmap.get(1));
// 5. delete a key
hashmap.remove(2);
// 6. check if a key is in the hash map
if (!hashmap.containsKey(2)) {
    System.out.println("Key 2 is not in the hash map.");
}
// 7. get the size of the hash map
System.out.println("The size of hash map is: " + hashmap.size()); 
// 8. iterate the hash map
for (Map.Entry<Integer, Integer> entry : hashmap.entrySet()) {
    System.out.print("(" + entry.getKey() + "," + entry.getValue() + ") ");
}
System.out.println("are in the hash map.");
// 9. clear the hash map
hashmap.clear();
// 10. check if the hash map is empty
if (hashmap.isEmpty()) {
    System.out.println("hash map is empty now!");
}

추가 정보 얻기 (키 제외)

From array of indices, return indices of two numbers such that they add up to specific target

이 경우 hashamp이 필요하고 저장값이 필요하며 hashmap에서 찾을 수 있는지 확인하십시오 target - current_value.

FAQ

정수 그룹, 주어진 목표의 인덱스 목록에 숫자를 추가하는 것을 되돌려줍니다

두 문자열이 동일한지 확인합니다.(첫 번째 문자열에서 두 번째 문자열로 입력한 다른 문자로 1문자 대체)

키 모으기

aggregate all information by key

이러한 문제를 해결하는 관건은 기존 키를 만났을 때 정책을 정하는 것이다. (예를 들어hashmap 값을 1로 늘리고 원시 값을 새 값으로 바꾸는 것?)

FAQ

문자열의 첫 번째 비중복 문자를 찾아서 색인을 되돌려줍니다. 그렇지 않으면 -1

을 되돌려줍니다.

해싱 키 설계

산열 키의 디자인은 원시 정보와hashmap이 사용하는 키 사이에 있습니다. building a mapping relationshipdeciding what the hash key in hashmap should be해시 키는 보증이 필요합니다

1. All values belong to the same group will be mapped in the same group.
2. Values which needed to be separated into different groups will not be mapped into the same group.

hash function fulfills criteria 1 but NOT 2영사 함수는 이 두 조건을 동시에 만족시켜야 한다.

예.

글자수수께끼
HashMap에서 그룹까지의 글자 수수께끼(예를 들어'먹기','먹기'같은 그룹,'하기'다른 그룹)
해시 키 맵은 정렬 문자열을 사용할 수 있습니다.eat와ate는 키 "aet"에 비칩니다.

자세히 보기

https://home.cse.ust.hk/~dekai/2012H/lectures/l32_hash.pdf
http://courses.csail.mit.edu/6.006/fall11/lectures/lecture10.pdf
http://www.cs.toronto.edu/~ylzhang/csc263w15/slides/lec05-hashing.pdf