해시테이블과 해시맵은 무엇이며 일반적인 사용 사례는 무엇입니까?

Question

최근에 이러한 용어를 여러 번 접했지만 해당 용어가 어떻게 작동하고 언제 일반적으로 구현되는지 매우 혼란스럽습니다.

Answer 1

글쎄요, 이렇게 생각해보세요.

간단한 인덱스 기반 데이터 구조인 배열을 사용하고 임의의 항목으로 채우는 경우 기본적으로 검색을 시작해야 하기 때문에 데이터로 채울수록 특정 항목을 찾는 작업이 점점 더 비용이 많이 듭니다. 원하는 것을 찾을 때까지 한쪽 끝을 다른 쪽 끝으로 향하게 하세요.

데이터에 더 빠르게 액세스하려면 일반적으로 배열을 정렬하고 이진 검색을 사용합니다.하지만 이렇게 하면 기존 값을 찾는 속도가 빨라지지만, 중간에 요소를 삽입해야 할 때 기존 요소를 이동해야 하므로 새 값을 삽입하는 속도가 느려집니다.

반면에 해시테이블에는 항목을 가져와 이를 숫자, 즉 해시 키로 줄이는 관련 기능이 있습니다.이 숫자는 배열의 인덱스로 사용되며 여기에 항목을 저장합니다.

해시테이블은 처음에는 비어 있는 상태로 시작하는 배열을 중심으로 회전합니다.비어 있다는 것은 길이가 0임을 의미하지 않으며 배열은 크기로 시작하지만 배열의 모든 요소에는 아무것도 포함되지 않습니다.

각 요소에는 두 가지 속성인 데이터와 데이터를 식별하는 키가 있습니다.예를 들어, 미국의 우편번호 목록은 우편번호 -> 이름 유형의 연결이 됩니다.이 함수는 키를 줄이지만 데이터는 고려하지 않습니다.

따라서 해시테이블에 무언가를 삽입하면 함수는 키를 숫자로 줄여 이 (빈) 배열에 대한 인덱스로 사용되며 여기에 데이터, 키 및 관련 데이터를 저장합니다.

그런 다음 나중에 키를 알고 있는 특정 항목을 찾고 싶으므로 동일한 함수를 통해 키를 실행하고 해시 키를 얻은 다음 해시 테이블의 특정 위치로 이동하여 거기에서 데이터를 검색합니다.

이론에 따르면 키를 해시 키, 해당 숫자로 줄이는 함수는 선형 검색보다 계산상 훨씬 저렴합니다.

일반적인 해시테이블에는 저장에 사용할 수 있는 요소 수가 무한하지 않으므로 일반적으로 배열 크기에 맞는 인덱스까지 그 수를 더 줄입니다.이를 수행하는 한 가지 방법은 단순히 배열 크기와 비교하여 인덱스 모듈러스를 취하는 것입니다.크기가 10인 배열의 경우 인덱스 0-9는 인덱스에 직접 매핑되고 인덱스 10-19는 다시 0-9로 매핑됩니다.

일부 키는 해시 테이블의 기존 항목과 동일한 인덱스로 축소됩니다.이 시점에서 실제 키는 키의 데이터 유형 비교와 관련된 모든 규칙을 사용하여 직접 비교됩니다(예:예를 들어 일반적인 문자열 비교).완전히 일치하는 경우 새 데이터를 무시하거나(이미 존재함) 덮어쓰거나(해당 키에 대한 이전 데이터 대체) 추가(다중 값 해시 테이블)합니다.일치하는 항목이 없으면 즉, 해시 키는 동일했지만 실제 키는 그렇지 않았음을 의미하며 일반적으로 해당 키+데이터를 저장할 새 위치를 찾습니다.

충돌 해결에는 다양한 구현이 있으며 가장 간단한 방법은 배열의 다음 빈 요소로 이동하는 것입니다.하지만 이 간단한 솔루션에는 다른 문제가 있으므로 올바른 해결 알고리즘을 찾는 것도 해시테이블에 대한 좋은 연습입니다.

해시테이블은 완전히 채워지거나 거의 채워지면 커질 수 있으며 이는 일반적으로 새 크기의 새 배열을 만들고 모든 인덱스를 한 번 더 계산한 다음 항목을 새 배열에 배치하여 수행됩니다. 위치.

키를 숫자로 줄이는 함수는 선형 값을 생성하지 않습니다."AAA"는 1이 되고 "AAB"는 2가 되므로 해시테이블은 일반적인 값으로 정렬되지 않습니다.

해당 주제에 대한 좋은 위키피디아 기사도 있습니다. 여기.

Answer 2

Lassevk의 대답은 매우 좋지만 너무 많은 세부 사항을 포함 할 수 있습니다. 다음은 경영진 요약입니다. 그래요 의도적으로 특정 관련성을 생략합니다 시간의 99%를 안전하게 무시할 수있는 정보.

거기 있습니다 중요한 차이는 없습니다 해시 테이블과 해시 맵 사이의 시간의 99%.

해시 테이블은 마법입니다

진지하게. 그 모든 것은 마법의 데이터 구조입니다 세 가지를 보장합니다. (예외가 있습니다. 언젠가 그들을 배우는 것을 배우는 것은 크게 무시할 수 있습니다.)

1) 해시 테이블의 모든 것은 쌍의 일부입니다. 열쇠 그리고 a 값. 작업중인 키를 지정하여 데이터를 입력하고 나옵니다.

2) 해시 테이블에서 단일 키로 무엇이든하는 경우 멍청하게 빠릅니다. 이것은 그것을 암시합니다 put(key,value), get(key), contains(key), 그리고 remove(key) 모두 정말 빠릅니다.

3) 일반 해시 테이블 #2에 나열되지 않은 일을하는 데 실패합니다! ( "실패"에 의해, 우리는 그들이 느리게 느리다는 것을 의미합니다.)

해시 테이블은 언제 사용합니까?

해시 테이블을 사용합니다 그들의 마법이 우리의 문제에 맞을 때.

예를 들어, 캐싱 예를 들어, 대학에 45,000 명의 학생들이 있으며 일부 프로세스는 모두 기록을 유지해야한다고 가정 해 봅시다. ID 번호별로 학생을 정기적으로 언급하면 ID => student 캐시는 탁월한 의미가 있습니다. 이 캐시에 최적화하는 작업은 다음과 같습니다 빠른 조회.

해시는 또한 매우 유용합니다 데이터 간의 관계 저장 당신이 전체 돼지를 가고 물체를 자체적으로 바꾸고 싶지 않을 때. 예를 들어, 과정 등록 중에 학생들을 수업과 관련이있는 것이 좋습니다. 그러나 어떤 이유로 든 학생들이 그에 대해 알기를 원하지 않을 수도 있습니다. a studentToClassRegistration 해시하고 당신이해야 할 일을하는 동안 주위에 보관하십시오.

그들은 또한 a 데이터 구조에 대한 첫 번째 선택 다음 중 하나를 수행 해야하는 경우를 제외하고.

해시 테이블을 사용하지 않을 때

요소를 반복하십시오. 해시 테이블은 일반적으로 반복을 잘하지 않습니다. (일반적인 것, 즉, 특정 구현에는 때때로 반복을 덜 빨아내는 데 사용되는 링크 된 목록이 포함되어 있습니다. 예를 들어 Java, LinkedHashMap 키나 가치를 빨리 반복 할 수 있습니다.)

정렬. 반복 할 수 없다면 정렬도 왕의 고통입니다.

가치에서 열쇠로 이동합니다. 사용 둘 해시 테이블. 날 믿어, 난 그냥 당신에게 많은 고통을 구했다.

Answer 3

Java의 관점에서 이야기하는 경우, 객체 추가, 삭제 및 업데이트를 허용하는 컬렉션이며 내부적으로 알고리즘을 사용하는 컬렉션입니다.

그러나 우리가 Java와 관련하여 대화를 나누면 해시블이 본질적으로 동기화되므로 해시 맵은 스레드 안전 수집이 아니며 스레드 안전을 유지한다는 것입니다.

동기화 외에도 객체를 저장하고 검색하는 내부 메커니즘은 두 경우 모두 해싱입니다.

해싱이 어떻게 작동하는지 확인 해야하는 경우 데이터 스트러터 및 해싱 기술에 대해 약간의 인터넷 검색을 권장합니다.

Answer 4

Hashtables/Hashmaps는 다른 값과 값 (명확한 목적으로 '키'라고 함)을 연결합니다. 당신은 그것들을 일종의 사전 (단어 : 정의) 또는 데이터베이스 레코드 (키 : 데이터)로 생각할 수 있습니다.