>> ROB 보덴 : 안녕하세요.
롭 해요, 그리고하자 해시 이 솔루션 중.
그래서 여기에 우리가 구현하는거야 일반적인 해시 테이블.
우리는 볼 우리의 해시의 구조체 노드 표는 다음과 같이 할 것입니다.
따라서 문자의 단어를 가지고거야 크기 길이에 1을 더한 값의 배열입니다.
최대 이후 1을 잊지 마세요 사전에있는 단어는 45입니다
자, 그리고, 우리는거야 성을 위해 문자를 필요로
백 슬래시 0.
>> 그리고 각 우리의 해시 테이블 버킷 저장하는 것입니다
노드의 연결리스트.
우리는 여기에서 프로빙 선형을하지입니다.
그리고 순서에 따라 다음에 링크를 버킷에있는 요소는, 우리는 필요
구조체 노드 * 다음.
그래서 노드가 어떻게 생겼는지입니다.
지금, 여기에 선언은 우리의 해시 테이블의.
그것은 16,384 버킷을해야 할 것,하지만 것 그 수는 그리 중요하지 않습니다.
그리고 마지막으로, 우리는해야 할 것입니다 전역 변수 hashtable_size, 어떤
0으로 시작하는 것, 그리고 형입니다 추적을 유지하려고 얼마나 많은 단어
우리의 사전에 있었다.
괜찮아요.
>> 그럼 부하에 대해 살펴 보겠습니다.
그래서 부하를 발견, 그것은 부울을 반환합니다.
성공적이었다 경우 true를 반환 그렇지 않으면로드 및 false입니다.
그리고 const를 char *로 스타 소요 사전입니다 사전,
우리는 열려있다.
그래서 첫 번째 일이 우리가 할 것입니다.
우리의 사전은 fopen거야 읽기, 우리는해야 할 것입니다
그렇게하면 성공했는지 확인하기 위해 NULL을 반환, 우리는하지 않았다
성공적으로 사전을 열 우리는 false를 반환해야합니다.
>> 그러나 성공적으로 한 가정 열려있는, 우리가 읽고 싶은
사전.
우리는 몇 가지를 찾을 때까지 이렇게 반복 계속 이 탈옥 이유
우리가 볼 수 루프.
그래서 반복 유지하고, 지금 우리는거야 단일 노드를 MALLOC합니다.
그리고 물론, 우리는 검사 오류 필요 다시 mallocing 성공하지 않은 경우 그렇게
우리는 우리의 모든 노드를 언로드 할 이전의 malloc에​​ 일어난 닫습니다
사전 및 false를 반환합니다.
>> 그러나 무시, 가정 우리 성공, 우리는 fscanf 사용하려면
에서 하나의 단어를 읽을 수있는 우리의 우리의 노드에 사전.
그래서 엔트리> 단어를 기억하는 문자입니다 워드 크기의 버퍼 길이를 더한
우리는거야 하나 높은 단어를 저장
그래서 fscanf 1만큼을 반환하는 것입니다 성공적를 읽을 수있는로
파일에서 단어.
>> 오류 중 하나가 발생하거나 우리가 도달하면 파일의 단부는 저장하지 않는다
그렇지 않은 경우 경우 1을 반환 1을 반환, 우리는 마침내 휴식거야
이 while 루프 중.
그래서 우리는 볼 우리는 성공적이되면 에 단어를 읽을
항목 -> 단어, 우리는 해시거야 우리의 해시 함수를 사용하여 해당 단어.
이제 살펴 보자 해시 함수.
>> 그래서 당신이 정말로 필요로하지 않는다 이 문제를 이해하기.
실제로, 우리는 단지이 뽑아 인터넷에서 기능을 해시.
당신이 인식해야 할 유일한 일이다 이 const를 char *로 단어를 소요,
그래서 문자열을 입력 복용하고 있어요 출력으로 서명 int를 반환.
그래서 그 모든 해시 함수입니다, 그것은이다 입력에 소요, 그것은 당신에게 제공
해시 테이블에 인덱스.
우리가 NUM_BUCKETS으로 모딩 있다는 것을 알 수 그래서 해시 값이 반환
실제로 해시 테이블에 대한 인덱스이다 그리고 않는 이상하지 인덱스
어레이의 경계.
>> 그래서 해시 함수, 우리가 가고있는 점을 감안 우리가 읽고 단어를 해시
사전에서, 그리고, 우리는거야 그것을 사용하려면 삽입합니다
해시 테이블에 대한 엔트리.
이제, 해시 테이블 해시 전류 연결된 해시 테이블의 목록 및
그냥 NULL입니다 매우 가능합니다.
우리는에서 우리의 항목을 삽입 할 이 연결리스트의 시작 등
우리는 우리의 현재 항목을해야 할 것입니다 현재 어떤 해시 테이블을 가리
점, 그리고, 우리는 저장하는거야 해시의 해시 테이블
현재 항목.
>> 그래서이 두 줄이 성공적으로 삽입 의 시작 부분에 항목
그 인덱스에 연결된 목록 해시 테이블.
우리가 그와 함께 완료되면, 우리는 알고있다 우리는 다른 단어를 발견
사전과 우리는 다시 증가.
그래서 우리는 일을 계속하는 fscanf까지 마지막에 비 뭔가 1을 반환
하는 점은 우리가 필요한 것을 기억 무료 입장, 그래서 여기까지, 우리를 malloc으로 할당
항목 우리는 무언가를 읽으려고 사전에서.
그리고 우리는 성공적으로 읽지 않았다 사전에서 무엇인가하는
경우 우리는 항목을 비워야 실제로 해시 테이블에 넣어되지 않습니다
그리고 마지막으로 휴식.
>> 우리가 중단되면, 우리는 잘 볼 필요가 때문에 우리는이 탈옥 않았다
오류가 파일로부터 판독하거나시켰다 우리가 도달했기 때문에 우리는 탈출 않았다
파일 끝에?
오류가 발생했습니다 경우에, 우리는 원하는 부하가되지 않았기 때문에 false를 반환
성공, 그 과정에서 우리가 원하는 우리가 읽고 모든 단어를 언로드
과에서 사전 파일을 닫습니다.
우리가 성공 않은 가정, 우리 단지 여전히 사전을 닫을 필요
파일, 그리고 마지막으로 이후 true를 반환 우리는 성공적으로로드 한
사전.
그리고 그 부하 그거야.
>> 그래서 지금로드 해시 테이블 주어진 확인 다음과 같이 할 것입니다.
그래서,이 부울을 반환, 확인하는 표시하는 것입니다 여부
전달 된 문자 * 단어, 여부 전달 된 문자열은 우리의 사전에 있습니다.
그것은 사전에 그렇다면, 그이면 우리의 해시 테이블에, 우리는 돌아갑니다
사실, 그것이 아니라면, 우리는 false를 반환합니다.
이 전달 된 단어 감안할 때, 우린 단어를 해시하는 것.
>> 이제 인식 중요한 것은 부하에서, 우리는 알고 있었다 그 모든
단어는 소문자로 가고 있었다, 그러나 여기에서, 우리는 그렇게 확실하지 않다.
우리는 우리의 해시 함수를 살펴 경우, 실제로 우리 해시 함수
각 문자를 lowercasing된다 단어의.
그래서 관계없이 총액 단어, 우리의 해시 함수에가는
무엇에 대해 동일한 인덱스를 반환 대문자는 것 같습니다
완전히 소문자에 대해 반환 단어의 버전.
괜찮아요.
>> 그래서 우리의 인덱스입니다.
그것은이 단어에 대한 해시 테이블입니다.
이제, 루프이가는 링크 된 목록을 이상합니다
즉, 해당 인덱스에 있었다.
그래서 우리는 항목을 초기화하는 통지 해당 인덱스를 가리 키도록.
우리는 항목이 수행하는 동안 계속할 예정 동일하지 NULL, 기억이
우리의 연결리스트에서 포인터를 업데이트 항목은 다음 항목 -> 동일하므로이
우리의 현재의 엔트리 포인트 링크 된 목록에 다음 항목.
괜찮아요.
>> 따라서 링크 된 목록의 각 항목에 대한, 우리는 strcasecmp를 사용하는 것입니다.
그것은는 strcmp 아니기 때문에 다시 한번, 우리 소문자를 구별 가지 사례를하고 싶다.
그래서 우리는 단어를 비교 strcasecmp를 사용 그는이 함수에 전달 된
단어에 대한 그 이 항목에 있습니다.
그것은 0을 반환하면, 그 있었다 의미 우리가 할 경우 경기 일정,
true를 반환합니다.
우리는 성공적으로 발견 우리의 해시 테이블에있는 단어입니다.
>> 일치가 아니었다면, 우리는거야 다시 루프에 가서 봐
다음 항목.
그리고 우리는 거기있는 동안 루프를 계속합니다 이 연결 목록에있는 항목입니다.
우리가 중단하면 어떻게됩니까 루프이 중?
즉, 우리는 항목을 찾을 수 없습니다 의미 이 경우,이 단어를 일치
우리는 표시 할 false를 반환 우리의 해시 테이블은이 단어를 포함하지 않았다.
그리고 그 확인을 위해의.
괜찮아요.
>> 그래서 크기에 대해 살펴 보겠습니다.
이제, 크기는 매우 간단 될 것입니다 이후 각 단어에 대해, 부하 기억
우리는 우리가 글로벌을 증가 발견 변수 hashtable_size.
그래서 크기 기능은 있습니다 그 세계를 반환 할 것
변수, 그리고 바로 그거야.
>> 이제 마지막으로, 우리는 언로드 할 필요가 사전에 모든 것을 끝낼 번.
그래서 우리가 어떻게 그렇게 할거야?
바로 여기, 우리는 모든 것을 반복하고 우리의 해시 테이블의 버킷.
그래서 NUM_BUCKETS 버킷이 있습니다.
그리고 우리의 해시의 각 연결 목록 테이블, 우리는 반복 할거야
연결리스트의 전체 각 요소를 자유롭게.
이제, 우리는 조심해야합니다, 그래서 여기에 우리 의 임시 변수가
다음에 포인터를 저장 링크 된 목록의 요소입니다.
그리고 우리는 자유에가는거야 현재 요소.
>> 우리는 우리가 우리 때문에이 작업을 수행해야 할 필요가 다만 현재 요소에게 무료로 할 수
다음 다음 포인터에 액세스하려고 이후 한 번 우리는 그것을 해제
메모리는 무효가됩니다.
그래서 우리는 포인터를 주위에 유지해야 다음 요소는, 우리가 확보 할 수 있습니다
현재 요소, 그리고, 우리는 업데이트 할 수 있습니다 를 가리 키도록 현재의 요소
다음 요소.
>> 우리는 요소는 루프가 있습니다 동안 이 연결리스트에서.
우리는 모든 연결된 목록을 위해 그렇게 할 것이다 해시 테이블, 그리고 우리가 완료 한
그와 함께, 우리는 완전히 언로드했습니다 해시 테이블, 우리는 끝났어.
그래서 언로드에 대한에 지금까지 불가능 false를 반환하고, 우리가 수행하고, 우리
진실이 돌아갑니다.