나는 데이터 구조에 대해 배우고 있으며 모든 것이 매우 로켓 과학처럼 보입니다. 🙃 더 잘 이해할 수 있도록(Learning to Learn) 그 중 하나인 해시 테이블에 대한 작은 Zine을 만들었습니다 ⚡️

하단에서 리소스가 포함된 전체 서면 버전을 확인할 수 있지만 지금은 설명 버전을 확인하십시오!

부담없이 download the printable version . original handmade version도 있습니다.









... 그리고 이제 서면 버전...

해시 테이블의 마법

뭔데

🔍검색, ➕삽입, 🗑삭제에 가장 효율적인 데이터 구조.

모든 것을 평균적으로 O(1) 복잡성으로 수행합니다(즉, 사용 가능한 데이터의 크기에 관계없이 동일한 시간이 소요됨).

캐싱, 데이터베이스 검색 및 세트에 사용됩니다.

작동 방식

정렬되지 않은 고유 키 모음은 해싱 프로세스를 통해 값에 매핑됩니다.

키 가져오기 --> 해시 함수에서 실행 --> 해시를 생성하는 키

포르투갈어 --> ✨ --> 2
프랑스어 --------> ✨ --> 0
영어 -------> ✨ --> 3

... 테이블의 일치하는 인덱스("버킷"이라고도 함)에 추가합니다.


해시시
값


0
인사

1
-

2
올라

삼
안녕하십니까

해싱은 단방향입니다!

해시는 원래 키로 다시 변환할 수 없습니다.

예: "English"를 해싱하면 3이 반환되지만 3을 사용하면 "English"를 얻을 수 없습니다.

해시 함수는 다음을 충족해야 합니다.

🏎 빨리 달려라.

🧩 균일 분포.

💥 해시 충돌을 해결합니다.

충돌을 처리하는 방법?

충돌은 키가 이미 다른 키에서 가져온 해시(인덱스)에 해당할 때 발생합니다.

오픈 어드레싱

버킷을 이미 가져간 경우 사용하지 않는 버킷을 찾을 때까지 다른 버킷을 검사합니다.

💚 충돌 횟수가 적을 때 빠릅니다.

🚨 테이블은 키 수보다 작을 수 없습니다.

체이닝

버킷은 동일한 인덱스를 가진 여러 키를 사용할 수 있습니다.

💚 많은 충돌에 적합합니다.

🚨 공간 낭비(일부 버킷은 사용하지 않음).

💡FAQ

이상적인 부하율은 무엇입니까?

어떤 사람들은 0.7 정도라고 말합니다. 즉, 70개 항목이 있는 테이블에는 약 100개의 버킷이 있어야 합니다. 그러나 그것은 균형입니다. 버킷을 비울수록 속도가 빨라지고 충돌은 줄어들지만 더 많은 메모리가 사용됩니다.

동적 크기 조정이란 무엇입니까?

테이블이 균형을 잃을 때 발생합니다. 테이블이 너무 꽉 차거나 비어 있습니다. 테이블 크기를 조정하고 키를 다시 해시합니다.

최고의 해시 함수는 무엇입니까?

만능 솔루션은 없습니다. 속도와 배포 사이의 균형입니다.

좋은 해시 함수는 효율적인 해시 테이블의 비결입니다.

팁: 키가 정적이면 Perfect Hash Function을 사용하십시오. * 충돌 없음 * 빈 버킷 없음 *

언제 해시 테이블을 피해야 합니까?

검색이 기본 작업이 아닙니다.

요소를 반복해야 합니다.

중복된 키가 있습니다.

🎁 보너스: Javascript에서 간단한 해시 테이블 개념 적용!

😰 If 문을 사용할 때...

변수를 할당하기 위해 다른 시나리오를 처리할 때 if 지옥(또는 스위치 지옥)으로 끝납니다.

if(viewport === 'sm') {
    fontSize = 1.0;
} else if (viewport === 'md') {
    fontSize = 1.2;

} // else if ... else if ...

⚡️ 하지만 키:값 매핑을 사용하면...

더 깨끗한 코드로 옵션 수에 관계없이 직접 잠금 - O(1) 복잡성을 얻습니다. 얼마나 멋진가요?

const sizes = {

    sm: 1,
    md: 1.2,
    lg: 1.2

};

const fontSize = sizes[viewport];

시작하기 위한 리소스:

📝 Hash Tables - Wikipedia

🎥

🎥

읽어 주셔서 감사합니다!