[음악 재생]
>> DOUG 로이드 : 지금 당신 배열에 대해 많이 알고,
당신은 연결리스트에 대해 많이 알고있다.
그리고 우리는 논의했습니다 장점과 단점, 우리가했습니다
목록을 연결하는 논의 크고 작은 얻을 수 있습니다,
하지만 그들은 더 많은 크기를 차지합니다.
배열은 훨씬 더 간단한다 사용하지만, 그들은만큼에 제한있어
우리는의 크기를 설정할 필요로 처음에 배열
그리고 우리는 함께 붙어있어.
>> 하지만 우리가 꽤 많이했습니다,의 우리의 모든 주제를 소진
연결리스트와 배열에 대한.
아니면 우리가 있나요?
어쩌면 우리가 뭔가를 할 수 보다 창조적 인.
그리고 준다 그런 종류의 해시 테이블의 개념.
>> 그래서 해시 테이블에서 우리는 시도 할거야 연결리스트와 배열을 결합한다.
우리는 이점을거야 어레이, 랜덤 액세스 등에
그냥 배열에 갈 수있는 요소 (4) 또는 배열 요소 (8)
에서 반복 할 필요없이.
그건 바로, 꽤 빨리입니까?
>> 그러나 우리는 또한 우리의 데이터를 갖고 싶어 구조는 성장하고 축소 할 수 있습니다.
우리는 우리가하지 않는, 필요하지 않습니다 제한하려는.
그리고 우리가 할 수 있도록하려면 추가하고 물건을 제거하는
아주 쉽게, 어떤 당신이 기억하는 경우, 배열이 매우 복잡하다.
그리고 우리는이를 호출 할 수 있습니다 새로운 것은 해시 테이블.
>> 그리고 경우는, 올바르게 구현 우리는 일종의 취하고있어
두 데이터의 장점 이미 본 적이 구조,
배열과 연결리스트.
삽입을 시작할 수 있습니다 1 세타쪽으로 경향이있다.
세타 우리가 정말 논의하지 않은, 하지만 세타는 평균 경우입니다,
무슨 일이 실제로 일어날 것입니다.
당신은 항상 않을거야 최악의 시나리오를 가지고,
그리고 당신은 항상 가지고 않을거야 최선의 시나리오는, 그래서이다
평균 시나리오?
>> 그럼 평균 삽입 해시 테이블에
가까운 일정 시간에 얻을 시작할 수 있습니다.
그리고 삭제 얻을 수 있습니다 일정 시간에 닫습니다.
그리고 조회를 얻을 수 있습니다 일정 시간에 닫습니다.
That's-- 우리는 데이터가 없습니다 구조는 아직 그 작업을 수행 할 수 있습니다,
그래서이 이미 소리 꽤 좋은 점 등을들 수있다.
우리는 정말 완화 한 그 자체로 각각의 단점.
>> 이 성능을 얻으려면 하지만 우리를 업그레이드
우리가 추가하는 방법을 재고 할 필요가 구조로 데이터.
특히 우리가 원하는 데이터 자체는 우리에게
어디는 구조로 가야한다.
그리고 우리는이에 있다면 참조 할 필요가있는 경우 구조, 우리가 그것을 발견 할 필요가있는 경우,
우리는 데이터를보고 싶어 다시하고 효과적으로 할 수 수
데이터를 사용하여, 랜덤 액세스.
그냥보고에 의해 데이터 우리는해야한다
정확히 우리가있어 어디의 아이디어 해시 테이블에서 찾을 것.
>> 해시 이제 단점 테이블은 정말 걸이다
주문 또는 데이터를 정렬 꽤 나쁜.
그리고 사실, 당신은 시작하는 경우 주문하거나 정렬을 사용하는
데이터는 모두 손실 이점 이전에
삽입과 삭제의 관점에서했다.
시간에 가까워 질수록 N의 세타, 우리는 기본적했습니다
연결리스트로 회귀.
그래서 우리는 해시를 사용하려면 테이블 우리가 걱정하지 않는 경우
데이터를 정렬되어 있는지 여부를 확인합니다.
문맥있는 당신은 CS50에서 사용할 수 있습니다
당신은 아마 상관 없어 데이터를 정렬된다.
>> 그래서 해시 테이블의 조합이다 별개의 두 조각
있는 우리는 잘 알고.
첫 번째 함수 인 우리는 일반적으로 해시 함수를 호출합니다.
그리고 해쉬 함수에 가고 일부 음이 아닌 정수를 반환하는
우리는 일반적으로 확인, 해시 코드를 호출?
두 번째 부분은 배열입니다 우리 형의 데이터 저장 능력
데이터 구조로 배치 할.
우리는에 보류합니다 지금은 목록 요소를 연결
단지의 기초부터 시작 그것의 주위에 당신의 머리를 얻기 위해 테이블​​을 해시,
그리고, 우리는 아마 타격 것 당신의 마음을 조금 때
함께 배열과 링크 목록을 결합한다.
>> 기본적인 생각하지만 우리는 일부 데이터를 가지고 있습니다.
우리는 데이터를 통해 실행 해시 함수.
그리고 데이터 처리 그것은 확인 번호를 뱉어?
그리고 그 수와 우리는 단지 데이터를 저장
우리는에 저장할 그 위치에 배열입니다.
그래서 예를 들어 우리는 어쩌면이 문자열의 해시 테이블.
그것은 그래서, 10 요소를 가지고 우리는 10 문자열에 맞게 할 수 있습니다.
>> 이제 우리는 존 해시하려는 가정 해 봅시다.
존 그래서 데이터로 우리는 삽입 할 어딘가에이 해시 테이블에.
우리는 어디를 배치해야합니까?
그런데 일반적으로 배열 지금까지 우리는 아마
배열 위치 0에 넣어 것입니다.
하지만 지금 우리는이 새로운 해시 함수를 가지고있다.
>> 그리고 이제 우리는 존을 실행한다고 가정 해 봅시다 이 해시 함수를 통해
그리고 4 뱉어입니다.
우린 여기서 뭐 그건 존을 데려 가고 싶다는 것.
우리는 배열 위치에 존을 데려 가고 싶다는 4, 우리는 again-- 존 해시 경우 때문에
의 나중에에게 우리 말을하자 검색 및보고 싶어
요한은이 해시에있는 경우 우리가해야 할 모든 table--
동일한 해시를 통해 실행 기능, 숫자 4 점을 얻을
존을 찾​​을 수 바로 우리의 데이터 구조.
그건 꽤 좋은입니다.
>> 의 우리가 지금 이렇게 가정 해 봅시다 다시, 우리는 바울을 해시하고 싶다.
우리는 바울을 추가 할 이 해시 테이블에.
의이 시간은 우리가 실행한다고 가정 해 봅시다 해쉬 함수를 통해 폴
생성 된 해시 코드는 6입니다.
그런데 지금 우리는 바울을 넣을 수 있습니다 어레이 위치 6.
그리고 우리는 여부를 조회 할 필요가있는 경우 폴이 해시 테이블 인,
우리가해야 할 모든 폴 실행 해쉬 함수를 통해 다시
우리는 밖으로 다시 6을 얻을 것입니다.
>> 그리고 우리는 단지보고 배열 위치 (6)에서.
바울이 있습니까?
그렇다면, 그는 해시 테이블에 있습니다.
바울은하지 있습니까?
그는 해시 테이블에없는.
그것은 매우 간단합니다.
>> 이제 당신은 어떻게 해시 함수를 정의 할 수 있습니까?
그럼 정말 제한이 없습니다 가능한 해쉬 함수의 수입니다.
사실의 수는, 거기에 정말 인터넷에 정말 좋은 것.
의 수는 정말로있다 인터넷에 정말 나쁜 사람.
그것은 또한 아주 쉽게 나쁜 하나를 작성합니다.
>> 그래서 좋은를 구성하는 해시 기능, 오른쪽?
그럼 좋은 해시 함수는해야 데이터 만이 사용되는 해시,
및 데이터의 모든 해시된다.
그래서 우리는 anything-- 사용하지 않으려는 우리는 아무것도 포함하지 않는다
데이터 이외의 다른.
우리는 모든 데이터를 사용할.
우리는 단지 한 조각을 사용하지 않으 그것을, 우리는 모두 사용하고 싶습니다.
해시 함수해야 또한 결정합니다.
그게 무슨 뜻 이죠?
잘 그것은 즉, 때마다 우리 데이터의 동일한 부분을 통과
해시 함수로 우리 항상 같은 해시 코드를 얻을.
나는에 존을 통과하는 경우 해시 함수는 내가 4를 얻는다.
나는 그렇게 할 수 있어야한다 10,000 시간과 나는 항상 4를 얻을 수 있습니다.
그래서 임의의 숫자를 효과적으로 우리의 해시에 관여 할 수 tables--
우리의 해시 함수에.
>> 해시 함수는해야 균일하게 데이터를 배포 할 수 있습니다.
때마다 당신은을 통해 데이터를 실행하는 경우 해시 함수는, 해시 코드 0을 얻을
맞아, 아마 그렇게 큰 아니에요?
당신은 아마 큰 원하는 해시 코드의 범위.
또한 일이 확산 될 수 테이블을 통해 밖으로.
또한이 경우에 정말 좋은 것 존과 요나단 같은 유사한 데이터,
아마 무게를 확산했다 해시 테이블의 다른 위치.
즉 좋은 장점이 될 것입니다.
>> 다음은 해시 함수의 예입니다.
나는 이번 일을 썼다.
그것은 특히 아니다 좋은 해시 함수
정말하지 않는 이유 지금에가는 부담.
하지만 당신은 여기 무슨 일이야 볼 수 있습니까?
우리는 변수를 선언하는 것 같다 합과 0이 그것을 설정했다.
그리고 분명히 내가 뭔가를하고 있어요 너무 오래 strstr과 [J]가 동일하지 않은 것처럼
0 백 슬래시합니다.
내가 거기 뭐하는 거지?
>> 이것은 기본적으로 또 다른입니다 [을 구현하는 방법은? strl?]
당신이했습니다 때 검출 문자열의 끝에 도달.
그래서 사실 필요가 없습니다 문자열의 길이를 계산
나는를 쳤을 때 그냥 사용하고 있습니다 백 슬래시 0 문자 내가 아는
나는 문자열의 끝에 도달했습니다.
그리고 나는 계속거야 해당 문자열을 반복,
strstr과 [J]를 추가하면에서 다음 합계,하고 하루의 끝은 합계 모드를 반환하는 것
HASH_MAX.
>> 기본적으로이 모든 해시 기능까지 추가하고하고있다
의 ASCII 값의 모든 내 문자열은 다음 그건
일부 해시 코드를 반환 HASH_MAX에 의해 modded하게.
아마 크기의 내 배열의 오른쪽?
나는 해시를 받고 싶지 않아 코드 내 배열의 사이즈가 10 인 경우,
나는지고 ​​싶지 않아 아웃 해시 코드 11, 12,
13, 나는에 물건을 넣을 수 없습니다 그 어레이의 위치,
그 불법이 될 것이다.
나는 세그먼트 오류 고통을 것입니다.
>> 이제 여기에 또 다른 빠른 옆입니다.
일반적으로 당신은 아마하지 않을거야 자신의 해시 함수를 작성하려고합니다.
실제로 약간입니다 예술이 아니라 과학입니다.
그리고 그들로가는 많은있다.
내가 말한 것처럼 인터넷은, 가득 정말 좋은 해시 함수,
당신은 인터넷을 사용해야합니다 정말 때문에 해시 함수를 찾을 수
단지 종류의 필요를 시간의 낭비는 자신을 만들 수 있습니다.
>> 당신은 간단한 것들을 쓸 수 있습니다 테스트 목적.
그러나 실제로하려고 할 때는 데이터를 해싱하고 저장 시작
당신이있어 해시 테이블에 아마 할 것
생성 된 일부 기능을 사용 당신을 위해, 그 인터넷에 존재합니다.
당신은 확신 할 경우 당신의 소스를 인용합니다.
이유에가 없습니다 여기에 아무것도 표절.
>> 컴퓨터 과학 커뮤니티입니다 확실히 값을 성장, 정말
오픈 소스, 그리고 정말 중요합니다 당신의 소스를 인용 할 수 있도록 사람들
에 대한 속성을 얻을 수 있습니다 그들이있어 작업
지역 사회의 이익을 위해 일을.
그래서 항상 sure-- 수 뿐 아니라 해시에 대한
기능, 그러나 일반적으로 때를 외부 소스 코드를 사용,
항상 당신의 소스를 인용.
한 사람에게 신용을 줘 작품의 일부는 그래서 당신은 할 필요가 없습니다.
>> 확인 그래서이를 다시 방문하자 두 번째 해시 테이블.
우리가 떠나기 곳이다 우리가 삽입 된 후 해제
이 해시 테이블에 존과 폴.
여기서 문제를 볼 수 있습니까?
두 가지를 볼 수 있습니다.
그러나 특히, 당신을 이 가능한 문제를 볼?
>> 나는 무엇 링고 해시하고있는 경우 후 처리 밝혀
해쉬 함수를 통해 데이터 링고는 해시 코드 (6)를 생성합니다.
이미 데이터를 가지고 hashcode-- 배열 위치 (6).
그래서 아마 조금 될 것 지금 나에게 문제가, 오른쪽?
>> 우리는 충돌이를 호출합니다.
및 충돌시 발생하는 두 데이터의 조각들은 동일한 해시를 통해 실행할
함수는 동일한 해시를 산출.
아마도 우리는 여전히 모두 싶어 해시 테이블로 데이터 조각
그렇지 않으면 우리는 링고가 실행되지 않을 것이다 임의로 해쉬 함수를 통한.
우리는 아마도 싶어 그 배열에 링고.
>> 우리가 비록 그것을 어떻게, 그는 경우 바울 모두 수율 해시 코드 (6)?
우리는 바울을 덮어 싶지 않아, 우리는 바울이 너무가되고 싶어요.
그래서 우리가 얻을 수있는 방법을 찾을 필요 해시 테이블에 요소가
여전히 우리의 빠른을 유지 삽입 및 훑어보기까지.
그리고 그것을 처리하는 한 가지 방법은이다 프로빙 선형라는 뭔가.
>> 우리가있는 경우이 방법을 사용하여 충돌, 잘, 우리는 무엇을해야합니까?
그런데 우리는 배열 위치에 그를 넣어 수 없습니다 6, 또는 어떤 해시 코드 생성,
의는 해시 플러스 1에 집어 넣어 보자.
그리고 전체하자의 경우 해시 플러스 2에서 그를 넣어.
이 존재의 장점 그는 있다면 정확히 우리는 그가 생각하는 경우,
우리는 검색을 시작해야한다, 어쩌면 우리는 너무 멀리 갈 필요가 없습니다.
어쩌면 우리는 검색하지 않아도 해시 테이블의 모든 N 개의 소자.
어쩌면 우리는 검색해야 그 중 몇 가지.
>> 그래서 우리는 여전히쪽으로 경향이있어 평균 경우는 1에 가까운 대 인 것을
N에 가까운, 그래서 아마 그 작동합니다.
그럼 방법이를 보자 현실에서 작동 할 수 있습니다.
그리고 어쩌면 우리가 감지 할 수 있는지 보자 여기에 발생할 수있는 문제.
>> 의 우리가 바트 해시 가정 해 봅시다.
그래서 지금 우리는 새로운 설정을 실행하는거야 해쉬 함수를 통해 문자열,
우리는 해시를 통해 바트를 실행 기능, 우리는 해시 코드 (6)을 얻는다.
우리는 좀 봐, 우리는 6가 참조 빈, 그래서 우리가 바트를 넣을 수 있습니다.
>> 이제 우리는 리사와 그 해시 또한 해시 코드 (6)를 생성한다.
그런데 지금 우리는이를 사용하고 있는지 선형, 우리는 6시에 시작하는 방법을 프로빙
우리는 6가 가득 것을 알 수있다.
우리는 6 리사를 넣을 수 없습니다.
그래서 우리는 어디에 가야합니까?
의 7에 가자.
(7)의 빈, 그래서 작품을.
그래서이 리사를 만들어 보자.
>> 이제 우리는 호머 해시 우리는 7 얻을.
확인을 잘 우리는 알고있다 (7)의 전체가 지금, 우리가 호머를 넣을 수 없습니다.
그럼 8로 가자.
8은 사용할 수 있습니까?
그래, 그리고 7 ~ 8의 가까운, 그래서 경우 우리는 우리가있어 검색을 시작해야
너무 멀리 갈 필요하지 않을.
그래서의 8에서 호머을 만들어 보자.
>> 이제 우리는 해시 매기와 3 반환, 선 (善) 감사합니다
우리는 단지이 매기를 넣을 수있어.
우리는 어떤 작업을 수행 할 필요가 없습니다 종류의 프로빙.
이제 우리는 마지 해시하고, 마지는 6을 반환합니다.
>> 그럼 6, 8이 가득, 7가 가득, 가득 9, 모든 권리 (9)가 비어있는, 하나님 께 감사를드립니다.
나는 9시에 마지를 넣을 수 있습니다.
이미 우리는 우리가 시작하는 것을 볼 수있다 우린 지금이 문제가있는
종류의 일을 스트레칭하기 시작 의 멀리 자신의 해시 코드에서.
그리고 1의 세타, 그 평균 일정 시간 인 경우,
조금 more--를 얻을 시작 더 작은 경향 시작
N의 세타으로.
우리는을 잃게하기 시작하고 해시 테이블을 이용.
>> 우리가 방금 본이 문제 클러스터링이라고 무언가이다.
그리고 정말 나쁜거야 클러스터링은 당신이 한 번 지금
측면 두 가지 요소에 의해이 그것은 더욱 가능성있게 좌우,
당신은 두 번이 기회는거야
또 다른 충돌을 갖도록 해당 클러스터와,
클러스터는 하나 성장할 것이다.
그리고 당신은 성장하고 성장하겠습니다 충돌을 가진 당신의 가능성.
그리고 결국은 그냥 나쁜 같은 모든 데이터를 정렬하지.
>> 다른 문제는 비록 우리입니다 아직도, 지금까지 지금까지,
우리는 그저 봤는데 해시 테이블을 손쉽게 이해
우리는 여전히 10 문자열을위한 공간을 가지고있다.
우리는 해시를 계속하려면 스프링 필드의 시민,
우리는 거기에 그들 중 (10)를 얻을 수 있습니다.
그리고 우리는 시도하고 11 일 또는 12 일을 추가하는 경우 우리는 그들을 놓을 곳이 없습니다.
우리는 주변에서 회전 될 수있다 원 빈 자리를 찾기 위해 노력
우리는 어쩌면 박히 무한 루프에.
>> 그래서 아이디어를 빌려 이런 종류의 뭔가 체인했다.
그리고 이것은 우리가 가지고가는 곳이다 다시 그림으로 연결리스트.
어떤 경우 대신 저장 어레이 내의 데이터 자체
배열의 모든 요소 수 여러 개의 데이터를 보유?
잘 맞아, 이해가되지 않습니다?
우리는 그 배열 만 할 수있는 알고 배열의 각 요소를 잠시,
하나의 조각을 보유 할 수 있습니다 데이터 타입의 데이터.
>> 하지만 경우 해당 데이터 유형 연결리스트, 오른쪽입니까?
그래서 만약에 모든 배열의 요소였다
연결리스트의 헤드 포인터?
그리고 우리는 만들 수 그 연결리스트
및 임의로 그들을 성장 연결리스트가 수 있기 때문에
우리는 성장하고 더 많은 축소하는 배열을 수행 유연보다.
그래서 우리가 지금 사용하는 경우, 우리는 바로이 활용?
우리는이 사슬을 성장 시작 이러한 배열 위치가 부족합니다.
>> 이제 우리는 무한에 맞게 수 데이터의 양, 또는 무한하지
임의의 양 데이터, 우리의 해시 테이블에
적으로 실행하지 않고 충돌의 문제.
우리는 또한 제거했습니다 이렇게하면 클러스터링.
그리고 물론 우리는 우리가 삽입 할 때 알고 연결리스트로, 당신이 기억하는 경우
단독으로, 연결리스트에 우리의 비디오에서 연결리스트와 이중 연결리스트,
이는 일정 시간 운전이다.
우리는 단지 전면에 추가하고 있습니다.
>> 그리고 모양까지에 대해 잘 우리는 알고있다 즉, 연결리스트에서 찾아 볼
바로, 문제가 될 수있다?
우리는을 통해 검색 할 수있다 처음부터 끝까지.
더 무작위가 없습니다 링크 된 목록에 액세스 할 수 있습니다.
그러나 경우 대신 하나를 갖는의 연결 조회 N 아 것 목록,
우리는 지금 10 연결리스트를 가지고, 1,000 연결리스트,
지금은 10로 나눈 N의 O이야, 또는 n의 O를 1000으로 나눈 값.
>> 그리고 우리가 이야기하는 동안 이론적으로 복잡성에 대한
우리는 실시간으로, 상수를 무시 이러한 일들이 실제로 문제가 세계,
권리?
우리는 실제로 알 이런 그
10 배 빠른를 실행하려면, 1,000 배 빠른 속도로,
우리는 긴 하나를 배포하고 있기 때문에 1000 작은 체인에서 체인.
그래서 우리가 때마다 검색 할 우리가 할 수있는 그 체인 중 하나를 통해
우리가 상관 없어 999 체인을 무시 약, 단지 그 하나를 검색 할 수 있습니다.
>> 어떤에 평균에 1,000 시간이 짧아.
그래서 우리는 여전히 일종의 있습니다 이 경우 평균쪽으로 경향
일정 시간이되고 있지만, 단지 우리가 활용되기 때문에
몇 가지 큰 상수 요소로 나누어.
방법이 수도 보자 실제로 그래도 봐.
그래서 이것은 우리가 가진 해시 테이블이었다 우리는 해시 테이블을 선언하기 전에
문자열 (10)을 저장할 수 있었다.
우리는 더 이상 그렇게하지 ​​않을거야.
우리는 이미 알고있는 그 방법의 한계.
이제 우리의 해시 테이블 될 것 노드 (10), 포인터 배열
연결리스트의 머리에.
>> 그리고 지금은 널 (null)입니다.
그 10 포인터의 각각은 null입니다.
아무것도 우리에 없다 지금 테이블을 해시.
>> 이제 몇 가지를 넣어 시작하자 이 해시 테이블에 일.
그리고의는이 방법이 얼마나 보자 우리에게 약간의 혜택을 누릴 것.
의 지금 조이 해시 보자.
우리는 문자열 조이를 통해 실행됩니다거야 해시 함수 우리는 6을 반환합니다.
그런데 우리는 지금 무엇을해야합니까?
>> 글쎄 지금은 연결리스트와 협력, 우리는 배열 작동하지 않는 것입니다.
그리고 우리는 작업 할 때 연결리스트와 우리
우리는 동적으로 시작해야합니다 알고 공간과 건물 체인을 할당하는 단계를 포함한다.
즉 일종의 그 핵심이다 how--이다 연결리스트를 구축하는 요소.
그래서 동적으로하자 조이위한 공간을 할당,
다음의 체인에 그를 추가 할 수 있습니다.
>> 그래서 지금 우리가 무슨 짓을했는지 봐.
우리가 조이 해시 때 우리는 해시 코드 (6)을 얻었다.
배열 위치 6에서 이제 포인터 연결리스트의 머리를 가리키는,
그리고 지금은 만이다 연결리스트의 요소입니다.
그리고 그 노드에서 연결리스트는 조이입니다.
>> 우리가 조이를 볼 필요가 있다면 이후, 우리는 다시 조이 해시,
우리는 우리를하기 때문에 다시 6을 얻을 해시 함수는 결정적이다.
그리고 우리는 머리에서 시작 연결리스트의 지적
배열 위치에 의해 6, 우리는 반복 할 수
조이를 찾기 위해 노력하고 그 맞은 편.
그리고 우리는 만들 경우 우리의 효과적으로 테이블을 해시,
우리의 해시 함수를 효과적으로 물론 데이터를 배포하고,
평균 이들 각각 연결된 모든 어레이 위치리스트
경우의 크기 1/10 일 것이다 우리 단지 하나의 거대한로했다
그것의 모든 링크 된 목록입니다.
>> 우리는 거대한 연결된 것을 배포하는 경우 (10) 연결리스트에서리스트
각 목록은 1/10 크기가됩니다.
그리고 이렇게 10 배 빠른 를 통해 검색 할 수 있습니다.
그래서 다시이 작업을 수행 할 수 있습니다.
의 지금 로스 해시 보자.
>> 그리고 이제 우리가 그렇게 할 때 로스를 가정 해 봅시다 우리가 얻을 해시 코드는 2입니다.
그럼 이제 우리는 동적으로 할당 새로운 노드, 우리는 그 노드의 로스를 넣어
우리는 배열 위치 지금 말 2, null로 가리키는 대신,
링크의 머리를 가리키는 그의 유일한 노드 목록은 로스입니다.
그리고 우리는, 우리를이 한 번 더 할 수 레이첼 해시 및 해시 코드 4를 얻을 수 있습니다.
에 레이첼을 넣어, 새 노드를 MALLOC 노드 및 배열 위치를 말한다
4 이제 머리를 가리키는 그 연결리스트의
유일한 요소는 레이첼 될 일이.
>> 확인을하지만이 경우 발생 우리는 충돌이?
의 우리가 충돌을 처리하는 방법을 살펴 보자 별도의 체인 방법을 사용.
의 피비 해시 보자.
우리는 해시 코드 (6)을 얻는다.
앞의 예에서 우리는 단지 있었다 배열의 문자열을 저장하는 단계를 포함한다.
이 문제였다.
>> 우리는 소지품 싶지 않아 조이, 우리는 이미했습니다
우리는 약간의 클러스터링을 얻을 수 있음을 알 문제 우리가 시도하는 경우 단계
통해 프로브.
그러나 만약 우리가 그냥 가지 이 바로, 같은 방법으로 치료?
그냥 요소를 추가처럼 연결리스트의 머리에.
피비 용의 단지 malloc에​​ 공간을 보자.
>> 우리는 피비의 다음 포인터 점을 말할 것 연결리스트의 이전 머리에,
다음 6 단지를 가리키는 연결리스트의 새로운 머리.
그리고 지금 우리의 피비를 변경 한 봐.
우리는 지금 두 가지를 저장할 수 있습니다 해시 코드 6 요소,
우리는 어떤 문제가 발생하지 않습니다.
>> 즉, 거의 전부 체인에있다.
그리고 체인은 확실히 의 방법
당신이 경우에 가장 효과적 일 것 당신은 해시 테이블에 데이터를 저장한다.
그러나이 조합 배열과 연결리스트
실제로 함께 해시 테이블을 형성 극적으로 당신의 능력을 향상
대용량의 데이터를 저장하고 매우 신속하고 효율적으로 검색
데이터를 통해.
>> 하나는 여전히있다 거기에 데이터 구조
그조차 조금있을 수 있습니다 보장의 측면에서 더 나은
우리의 삽입, 삭제, 조회 시간도 빠릅니다.
그리고 우리는 시도에 비디오가 표시됩니다.
내가 더그 로이드 해요,이 CS50입니다.