일반적으로 사용되는 알고리즘: 해시 알고리즘

머리말

프로그래머는 일상적인 개발에서 업계에서 유명한 MD5, SHA, CRC 등과 같은 해싱 알고리즘에 익숙해야 합니다. 우리는 종종 맵을 사용하여 (키) , 값) 구조, 해시 알고리즘의 시간 복잡도 O(1)을 사용하여 프로그램 처리 효율성을 향상시킵니다. 또한 해시 알고리즘의 다른 응용 시나리오를 알고 있습니까?

1. 해시 알고리즘이란 무엇입니까?

해싱 알고리즘의 적용 시나리오를 이해하기 전에 먼저 해시(해시) 아이디어를 살펴보겠습니다. 해싱은 해싱 알고리즘을 통해 임의의 길이의 입력을 고정 길이 출력으로 변환하는 것입니다. (key), 출력은 해시 값, 즉 해시 값 hash(key)이고 해시 알고리즘은 hash() 함수입니다(Hash와 hash는 hash의 다른 번역입니다). 해시 테이블은 배열의 특징을 이용하여 첨자에 따라 데이터에 대한 무작위 접근을 지원합니다. O(1) 시간 복잡도를 달성합니다.

1.1 해시 충돌

현재 해시 알고리즘 MD5, SHA, CRC 등은 다른 해시 값을 가진 해시 함수를 달성할 수 없습니다. ​​서로 다른 키에 대응하는, 즉 서로 다른 키가 동일한 값으로 매핑되는 상황, 즉 해시 충돌이 발생하는 상황을 피할 수 없습니다. 더욱이 배열의 저장 공간이 제한되어 있기 때문에 해시 충돌도 증가합니다. 해시 충돌을 해결하는 방법은 무엇입니까? 우리가 일반적으로 사용하는 해시 충돌 해결 방법에는 개방형 주소 지정과 연결이라는 두 가지 유형이 있습니다.

1.1.1 개방형 주소 지정 방법

선형 검출을 통해 해시 테이블에서 빈 위치를 찾아 해시 값을 씁니다.

그림과 같이 834313이 해시의 303432 위치로 해시됩니다. 테이블에서 충돌이 발생하면 여유 위치를 찾을 때까지 해시 테이블을 순차적으로 탐색하여 834313이 기록됩니다. 해시 테이블에 여유 위치가 많지 않으면 정상적인 상황에서 해시 충돌 가능성이 크게 높아집니다. 해시 테이블에 일정 비율의 여유 슬롯이 있는지 확인하기 위해 최선을 다하겠습니다. 이때 로딩 계수를 사용하여 여유 슬롯 수를 나타냅니다. 해시 테이블의 인수 = 테이블에 채워진 요소 수/해시 테이블의 길이. 로드 팩터가 클수록 사용 가능한 위치가 줄어들고 충돌이 많아지며 해시 테이블의 성능이 저하됩니다.

데이터의 양이 상대적으로 적고 로드 팩터가 작은 경우 개방형 주소 지정 방식을 사용하는 것이 적합합니다. 이것이 바로 Java에서 ThreadLocalMap이 해시 충돌을 해결하기 위해 개방형 주소 지정 방식을 사용하는 이유입니다.

1.1.2 연결 목록 방법

연결 목록 방법은 더 일반적으로 사용되는 해시 충돌 해결 방법이며 더 간단합니다. 그림과 같이

해시 테이블에서 각 버킷/슬롯은 동일한 해시 값을 가진 모든 요소가 동일한 슬롯에 해당하는 연결 목록에 배치됩니다. 충돌이 발생하면 연결 목록의 길이도 길어집니다. 해시 값을 쿼리하려면 연결 목록을 순회해야 합니다. 이때 쿼리 효율성은 O(1)에서 O(n)으로 저하됩니다.

해시 충돌을 해결하는 이 방법은 큰 개체와 많은 양의 데이터가 있는 해시 테이블에 더 적합합니다. 또한 HashMap을 더욱 최적화하기 위해 연결된 목록 대신 레드-블랙 트리를 사용하는 등의 더 많은 최적화 전략을 지원합니다. jdk1.8, 레드-블랙 트리(red-black tree)가 도입되었습니다. 연결 리스트의 길이가 너무 길면(기본값이 8을 초과함) 이때 연결 리스트가 레드-블랙 트리로 변환됩니다. HashMap의 성능을 향상시키기 위해 빠르게 추가, 삭제 및 수정하는 데 사용할 수 있습니다. 레드-블랙 트리 노드의 수가 8보다 작을 때 레드-블랙 트리는 연결된 리스트로 변환됩니다. 데이터가 상대적으로 작기 때문에 레드-블랙 트리는 균형을 유지해야 하며 연결 ​​목록과 비교할 때 성능 이점이 분명하지 않습니다.

2. 해시 알고리즘의 적용 시나리오

2.1 보안 암호화

암호화에 가장 일반적으로 사용되는 해시 알고리즘은 MD5(MD5 Message-Digest Algorithm) 및 SHA(Secure Hash Algorithm)를 사용하여 계산됩니다. 해시의 특성상 원본 데이터를 역으로 추론하기 어렵기 때문에 암호화 목적을 달성할 수 없습니다.

MD5를 예로 들면, 해시 값은 최대 2^128개의 데이터를 나타낼 수 있는 고정된 128비트 바이너리 문자열입니다. 이 데이터는 이미 해시 충돌 가능성이 1/2^ 미만입니다. 128. 이 MD5와 동일한 다른 데이터를 철저한 방법으로 찾으려면 소요되는 시간이 천문학적이어야 하므로 제한된 시간 내에 해시 알고리즘을 해독하는 것은 여전히 ​​어렵고 암호화 효과도 달성합니다.

2.2 데이터 검증

해시 함수의 데이터 감지 기능을 사용하면 네트워크 전송 중 데이터가 올바른지 검증하고 악의적인 변조를 방지할 수 있습니다.

2.3 해시 함수

는 해시 함수의 비교적 균일한 분포 특성을 활용하고, 해시 값을 데이터 저장소의 위치 값으로 사용하여 데이터가 컨테이너 내에 고르게 분포되도록 합니다.

2.4 로드 밸런싱

해시 알고리즘을 사용하여 클라이언트 ID 주소 또는 세션 ID의 해시 값을 계산하고, 얻은 해시 값과 서버 목록의 크기에 대해 모듈로 연산을 수행합니다. 라우팅되어야 합니다. 서버 번호에 도달했습니다.

2.5 데이터 샤딩

사용자의 검색 키워드를 기록하는 1T 로그 파일이 있다고 가정합니다. 각 키워드가 검색된 횟수를 빠르게 계산하고 싶습니다. 데이터의 양이 상대적으로 커서 한 머신의 메모리에 넣기가 어렵습니다. 한 머신에 배치하더라도 처리 시간이 매우 길어집니다. 이 문제를 해결하려면 먼저 데이터를 조각화하고 그런 다음 여러 기계를 사용하여 처리 속도를 높이십시오.

구체적인 아이디어는 다음과 같습니다. 처리 속도를 향상시키기 위해 n개의 기계를 병렬 처리에 사용합니다. 검색 기록의 로그 파일에서 각 검색 키워드를 차례로 분석하고 해시 함수를 통해 해시 값을 계산한 후 최종 값은 이렇게 할당해야 하는 기계 번호입니다. 해시 값 동일한 값을 가진 검색 키워드는 동일한 머신에 할당되며, 각 머신은 키워드의 발생 횟수를 별도로 계산하고 최종 결과를 결합합니다. 사실 여기에서의 처리과정은 맵리듀스의 기본 설계 아이디어이기도 하다.

2.6 분산 저장소

대량의 데이터를 캐시해야 하는 상황에서는 캐시 머신 한 대로는 절대 부족하므로 여러 머신에 데이터를 분산시켜야 합니다. 이때 이전 샤딩 아이디어를 사용할 수 있습니다. 즉, 해시 알고리즘을 사용하여 데이터의 해시 값을 얻은 다음 머신 수의 모듈로를 취하여 저장해야 하는 캐시 머신 번호를 얻을 수 있습니다.

그러나 데이터가 증가하면 원래의 10개 머신은 더 이상 감당할 수 없어 확장해야 합니다. 이때 모든 데이터 해시 값을 다시 계산한 다음 올바른 머신으로 이동하면 것과 같습니다. 데이터가 갑자기 무효화되어 캐시에 침투하여 소스로 돌아가게 되면 눈사태 효과가 발생하여 데이터베이스가 압도될 수 있습니다. 모든 데이터를 이동하지 않고 새 캐시 머신을 추가하려면 일관된 해시 알고리즘이 더 나은 선택입니다. 주요 아이디어는 다음과 같습니다. kge 머신이 있고 데이터의 해시 값 범위가 [0, Max]라고 가정합니다. 전체 범위를 m개의 작은 간격으로 나눕니다.(m은 k보다 훨씬 큼) 각 기계는 m/k 작은 간격을 담당합니다. 새 기계가 합류하면 원래 기계에서 특정 작은 간격의 데이터를 전송합니다. 이를 새 머신에 저장하면 모든 데이터를 다시 해시하고 이동할 필요가 없을 뿐만 아니라 각 머신의 데이터 양의 균형을 유지할 수도 있습니다.

3. 마지막에 작성

사실 git commit id 등 해쉬 알고리즘의 응용은 많습니다. 많은 응용은 기본 데이터 구조이기도 한 알고리즘의 이해와 확장에서 나옵니다. 가치의 구체화는 우리의 작업에서 그것을 천천히 이해하고 경험하도록 요구합니다.

추천 튜토리얼: "Java Tutorial"

위 내용은 일반적으로 사용되는 알고리즘: 해시 알고리즘의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!