1
00:00:00,000 --> 00:00:11,856

2
00:00:11,856 --> 00:00:13,050
>> ROB 보덴 : 안녕하세요.

3
00:00:13,050 --> 00:00:16,210
롭 해요, 그리고하자 해시
이 솔루션 중.

4
00:00:16,210 --> 00:00:20,070
그래서 여기에 우리가 구현하는거야
일반적인 해시 테이블.

5
00:00:20,070 --> 00:00:24,090
우리는 볼 우리의 해시의 구조체 노드
표는 다음과 같이 할 것입니다.

6
00:00:24,090 --> 00:00:28,710
따라서 문자의 단어를 가지고거야
크기 길이에 1을 더한 값의 배열입니다.

7
00:00:28,710 --> 00:00:32,259
최대 이후 1을 잊지 마세요
사전에있는 단어는 45입니다

8
00:00:32,259 --> 00:00:35,110
자, 그리고, 우리는거야
성을 위해 문자를 필요로

9
00:00:35,110 --> 00:00:37,070
백 슬래시 0.

10
00:00:37,070 --> 00:00:40,870
>> 그리고 각 우리의 해시 테이블
버킷 저장하는 것입니다

11
00:00:40,870 --> 00:00:42,320
노드의 연결리스트.

12
00:00:42,320 --> 00:00:44,420
우리는 여기에서 프로빙 선형을하지입니다.

13
00:00:44,420 --> 00:00:48,430
그리고 순서에 따라 다음에 링크를
버킷에있는 요소는, 우리는 필요

14
00:00:48,430 --> 00:00:51,110
구조체 노드 * 다음.

15
00:00:51,110 --> 00:00:53,090
그래서 노드가 어떻게 생겼는지입니다.

16
00:00:53,090 --> 00:00:56,180
지금, 여기에 선언은
우리의 해시 테이블의.

17
00:00:56,180 --> 00:01:01,910
그것은 16,384 버킷을해야 할 것,하지만 것
그 수는 그리 중요하지 않습니다.

18
00:01:01,910 --> 00:01:05,450
그리고 마지막으로, 우리는해야 할 것입니다
전역 변수 hashtable_size, 어떤

19
00:01:05,450 --> 00:01:08,640
0으로 시작하는 것, 그리고 형입니다
추적을 유지하려고 얼마나 많은 단어

20
00:01:08,640 --> 00:01:10,080
우리의 사전에 있었다.

21
00:01:10,080 --> 00:01:10,760
괜찮아요.

22
00:01:10,760 --> 00:01:13,190
>> 그럼 부하에 대해 살펴 보겠습니다.

23
00:01:13,190 --> 00:01:16,390
그래서 부하를 발견,
그것은 부울을 반환합니다.

24
00:01:16,390 --> 00:01:20,530
성공적이었다 경우 true를 반환
그렇지 않으면로드 및 false입니다.

25
00:01:20,530 --> 00:01:23,990
그리고 const를 char *로 스타 소요
사전입니다 사전,

26
00:01:23,990 --> 00:01:25,280
우리는 열려있다.

27
00:01:25,280 --> 00:01:27,170
그래서 첫 번째 일이
우리가 할 것입니다.

28
00:01:27,170 --> 00:01:30,420
우리의 사전은 fopen거야
읽기, 우리는해야 할 것입니다

29
00:01:30,420 --> 00:01:34,700
그렇게하면 성공했는지 확인하기 위해
NULL을 반환, 우리는하지 않았다

30
00:01:34,700 --> 00:01:37,440
성공적으로 사전을 열
우리는 false를 반환해야합니다.

31
00:01:37,440 --> 00:01:41,580
>> 그러나 성공적으로 한 가정
열려있는, 우리가 읽고 싶은

32
00:01:41,580 --> 00:01:42,400
사전.

33
00:01:42,400 --> 00:01:46,210
우리는 몇 가지를 찾을 때까지 이렇게 반복 계속
이 탈옥 이유

34
00:01:46,210 --> 00:01:47,570
우리가 볼 수 루프.

35
00:01:47,570 --> 00:01:51,780
그래서 반복 유지하고, 지금 우리는거야
단일 노드를 MALLOC합니다.

36
00:01:51,780 --> 00:01:56,800
그리고 물론, 우리는 검사 오류 필요
다시 mallocing 성공하지 않은 경우 그렇게

37
00:01:56,800 --> 00:02:00,660
우리는 우리의 모든 노드를 언로드 할
이전의 malloc에​​ 일어난 닫습니다

38
00:02:00,660 --> 00:02:02,590
사전 및 false를 반환합니다.

39
00:02:02,590 --> 00:02:07,440
>> 그러나 무시, 가정 우리
성공, 우리는 fscanf 사용하려면

40
00:02:07,440 --> 00:02:12,400
에서 하나의 단어를 읽을 수있는 우리의
우리의 노드에 사전.

41
00:02:12,400 --> 00:02:17,310
그래서 엔트리> 단어를 기억하는 문자입니다
워드 크기의 버퍼 길이를 더한

42
00:02:17,310 --> 00:02:20,300
우리는거야 하나
높은 단어를 저장

43
00:02:20,300 --> 00:02:25,280
그래서 fscanf 1만큼을 반환하는 것입니다
성공적를 읽을 수있는로

44
00:02:25,280 --> 00:02:26,750
파일에서 단어.

45
00:02:26,750 --> 00:02:31,030
>> 오류 중 하나가 발생하거나 우리가 도달하면
파일의 단부는 저장하지 않는다

46
00:02:31,030 --> 00:02:34,950
그렇지 않은 경우 경우 1을 반환
1을 반환, 우리는 마침내 휴식거야

47
00:02:34,950 --> 00:02:37,280
이 while 루프 중.

48
00:02:37,280 --> 00:02:42,770
그래서 우리는 볼 우리는 성공적이되면
에 단어를 읽을

49
00:02:42,770 --> 00:02:48,270
항목 -> 단어, 우리는 해시거야
우리의 해시 함수를 사용하여 해당 단어.

50
00:02:48,270 --> 00:02:49,580
이제 살펴 보자
해시 함수.

51
00:02:49,580 --> 00:02:52,430

52
00:02:52,430 --> 00:02:55,610
>> 그래서 당신이 정말로 필요로하지 않는다
이 문제를 이해하기.

53
00:02:55,610 --> 00:02:59,460
실제로, 우리는 단지이 뽑아
인터넷에서 기능을 해시.

54
00:02:59,460 --> 00:03:04,010
당신이 인식해야 할 유일한 일이다
이 const를 char *로 단어를 소요,

55
00:03:04,010 --> 00:03:08,960
그래서 문자열을 입력 복용하고 있어요
출력으로 서명 int를 반환.

56
00:03:08,960 --> 00:03:12,360
그래서 그 모든 해시 함수입니다, 그것은이다
입력에 소요, 그것은 당신에게 제공

57
00:03:12,360 --> 00:03:14,490
해시 테이블에 인덱스.

58
00:03:14,490 --> 00:03:18,530
우리가 NUM_BUCKETS으로 모딩 있다는 것을 알 수
그래서 해시 값이 반환

59
00:03:18,530 --> 00:03:21,730
실제로 해시 테이블에 대한 인덱스이다
그리고 않는 이상하지 인덱스

60
00:03:21,730 --> 00:03:24,320
어레이의 경계.

61
00:03:24,320 --> 00:03:27,855
>> 그래서 해시 함수, 우리가 가고있는 점을 감안
우리가 읽고 단어를 해시

62
00:03:27,855 --> 00:03:31,700
사전에서, 그리고, 우리는거야
그것을 사용하려면 삽입합니다

63
00:03:31,700 --> 00:03:33,750
해시 테이블에 대한 엔트리.

64
00:03:33,750 --> 00:03:38,830
이제, 해시 테이블 해시 전류
연결된 해시 테이블의 목록 및

65
00:03:38,830 --> 00:03:41,410
그냥 NULL입니다 매우 가능합니다.

66
00:03:41,410 --> 00:03:45,640
우리는에서 우리의 항목을 삽입 할
이 연결리스트의 시작 등

67
00:03:45,640 --> 00:03:48,910
우리는 우리의 현재 항목을해야 할 것입니다
현재 어떤 해시 테이블을 가리

68
00:03:48,910 --> 00:03:54,030
점, 그리고, 우리는 저장하는거야
해시의 해시 테이블

69
00:03:54,030 --> 00:03:55,350
현재 항목.

70
00:03:55,350 --> 00:03:59,320
>> 그래서이 두 줄이 성공적으로 삽입
의 시작 부분에 항목

71
00:03:59,320 --> 00:04:02,270
그 인덱스에 연결된 목록
해시 테이블.

72
00:04:02,270 --> 00:04:04,900
우리가 그와 함께 완료되면, 우리는 알고있다
우리는 다른 단어를 발견

73
00:04:04,900 --> 00:04:07,800
사전과 우리는 다시 증가.

74
00:04:07,800 --> 00:04:13,960
그래서 우리는 일을 계속하는 fscanf까지
마지막에 비 뭔가 1을 반환

75
00:04:13,960 --> 00:04:18,560
하는 점은 우리가 필요한 것을 기억
무료 입장, 그래서 여기까지, 우리를 malloc으로 할당

76
00:04:18,560 --> 00:04:21,329
항목 우리는 무언가를 읽으려고
사전에서.

77
00:04:21,329 --> 00:04:24,110
그리고 우리는 성공적으로 읽지 않았다
사전에서 무엇인가하는

78
00:04:24,110 --> 00:04:27,440
경우 우리는 항목을 비워야
실제로 해시 테이블에 넣어되지 않습니다

79
00:04:27,440 --> 00:04:29,110
그리고 마지막으로 휴식.

80
00:04:29,110 --> 00:04:32,750
>> 우리가 중단되면, 우리는 잘 볼 필요가
때문에 우리는이 탈옥 않았다

81
00:04:32,750 --> 00:04:35,840
오류가 파일로부터 판독하거나시켰다
우리가 도달했기 때문에 우리는 탈출 않았다

82
00:04:35,840 --> 00:04:37,120
파일 끝에?

83
00:04:37,120 --> 00:04:40,150
오류가 발생했습니다 경우에, 우리는 원하는
부하가되지 않았기 때문에 false를 반환

84
00:04:40,150 --> 00:04:43,260
성공, 그 과정에서 우리가 원하는
우리가 읽고 모든 단어를 언로드

85
00:04:43,260 --> 00:04:45,670
과에서 사전 파일을 닫습니다.

86
00:04:45,670 --> 00:04:48,740
우리가 성공 않은 가정, 우리 단지
여전히 사전을 닫을 필요

87
00:04:48,740 --> 00:04:51,970
파일, 그리고 마지막으로 이후 true를 반환
우리는 성공적으로로드 한

88
00:04:51,970 --> 00:04:53,040
사전.

89
00:04:53,040 --> 00:04:54,420
그리고 그 부하 그거야.

90
00:04:54,420 --> 00:04:59,020
>> 그래서 지금로드 해시 테이블 주어진 확인
다음과 같이 할 것입니다.

91
00:04:59,020 --> 00:05:02,690
그래서,이 부울을 반환, 확인하는
표시하는 것입니다 여부

92
00:05:02,690 --> 00:05:07,530
전달 된 문자 * 단어, 여부
전달 된 문자열은 우리의 사전에 있습니다.

93
00:05:07,530 --> 00:05:10,530
그것은 사전에 그렇다면, 그이면
우리의 해시 테이블에, 우리는 돌아갑니다

94
00:05:10,530 --> 00:05:13,380
사실, 그것이 아니라면,
우리는 false를 반환합니다.

95
00:05:13,380 --> 00:05:17,770
이 전달 된 단어 감안할 때, 우린
단어를 해시하는 것.

96
00:05:17,770 --> 00:05:22,020
>> 이제 인식 중요한 것은
부하에서, 우리는 알고 있었다 그 모든

97
00:05:22,020 --> 00:05:25,820
단어는 소문자로 가고 있었다,
그러나 여기에서, 우리는 그렇게 확실하지 않다.

98
00:05:25,820 --> 00:05:29,510
우리는 우리의 해시 함수를 살펴 경우,
실제로 우리 해시 함수

99
00:05:29,510 --> 00:05:32,700
각 문자를 lowercasing된다
단어의.

100
00:05:32,700 --> 00:05:37,580
그래서 관계없이 총액
단어, 우리의 해시 함수에가는

101
00:05:37,580 --> 00:05:42,270
무엇에 대해 동일한 인덱스를 반환
대문자는 것 같습니다

102
00:05:42,270 --> 00:05:45,280
완전히 소문자에 대해 반환
단어의 버전.

103
00:05:45,280 --> 00:05:45,950
괜찮아요.

104
00:05:45,950 --> 00:05:47,410
>> 그래서 우리의 인덱스입니다.

105
00:05:47,410 --> 00:05:49,790
그것은이 단어에 대한 해시 테이블입니다.

106
00:05:49,790 --> 00:05:52,940
이제, 루프이가는
링크 된 목록을 이상합니다

107
00:05:52,940 --> 00:05:55,000
즉, 해당 인덱스에 있었다.

108
00:05:55,000 --> 00:05:59,630
그래서 우리는 항목을 초기화하는 통지
해당 인덱스를 가리 키도록.

109
00:05:59,630 --> 00:06:03,480
우리는 항목이 수행하는 동안 계속할 예정
동일하지 NULL, 기억이

110
00:06:03,480 --> 00:06:08,350
우리의 연결리스트에서 포인터를 업데이트
항목은 다음 항목 -> 동일하므로이

111
00:06:08,350 --> 00:06:13,840
우리의 현재의 엔트리 포인트
링크 된 목록에 다음 항목.

112
00:06:13,840 --> 00:06:14,400
괜찮아요.

113
00:06:14,400 --> 00:06:19,150
>> 따라서 링크 된 목록의 각 항목에 대한,
우리는 strcasecmp를 사용하는 것입니다.

114
00:06:19,150 --> 00:06:23,780
그것은는 strcmp 아니기 때문에 다시 한번, 우리
소문자를 구별 가지 사례를하고 싶다.

115
00:06:23,780 --> 00:06:28,830
그래서 우리는 단어를 비교 strcasecmp를 사용
그는이 함수에 전달 된

116
00:06:28,830 --> 00:06:31,860
단어에 대한 그
이 항목에 있습니다.

117
00:06:31,860 --> 00:06:35,570
그것은 0을 반환하면, 그 있었다 의미
우리가 할 경우 경기 일정,

118
00:06:35,570 --> 00:06:36,630
true를 반환합니다.

119
00:06:36,630 --> 00:06:39,590
우리는 성공적으로 발견
우리의 해시 테이블에있는 단어입니다.

120
00:06:39,590 --> 00:06:43,040
>> 일치가 아니었다면, 우리는거야
다시 루프에 가서 봐

121
00:06:43,040 --> 00:06:43,990
다음 항목.

122
00:06:43,990 --> 00:06:47,640
그리고 우리는 거기있는 동안 루프를 계속합니다
이 연결 목록에있는 항목입니다.

123
00:06:47,640 --> 00:06:50,160
우리가 중단하면 어떻게됩니까
루프이 중?

124
00:06:50,160 --> 00:06:55,110
즉, 우리는 항목을 찾을 수 없습니다 의미
이 경우,이 단어를 일치

125
00:06:55,110 --> 00:07:00,220
우리는 표시 할 false를 반환 우리의
해시 테이블은이 단어를 포함하지 않았다.

126
00:07:00,220 --> 00:07:01,910
그리고 그 확인을 위해의.

127
00:07:01,910 --> 00:07:02,540
괜찮아요.

128
00:07:02,540 --> 00:07:04,790
>> 그래서 크기에 대해 살펴 보겠습니다.

129
00:07:04,790 --> 00:07:09,280
이제, 크기는 매우 간단 될 것입니다
이후 각 단어에 대해, 부하 기억

130
00:07:09,280 --> 00:07:12,880
우리는 우리가 글로벌을 증가 발견
변수 hashtable_size.

131
00:07:12,880 --> 00:07:15,830
그래서 크기 기능은 있습니다
그 세계를 반환 할 것

132
00:07:15,830 --> 00:07:18,150
변수, 그리고 바로 그거야.

133
00:07:18,150 --> 00:07:22,300
>> 이제 마지막으로, 우리는 언로드 할 필요가
사전에 모든 것을 끝낼 번.

134
00:07:22,300 --> 00:07:25,340
그래서 우리가 어떻게 그렇게 할거야?

135
00:07:25,340 --> 00:07:30,440
바로 여기, 우리는 모든 것을 반복하고
우리의 해시 테이블의 버킷.

136
00:07:30,440 --> 00:07:33,240
그래서 NUM_BUCKETS 버킷이 있습니다.

137
00:07:33,240 --> 00:07:37,490
그리고 우리의 해시의 각 연결 목록
테이블, 우리는 반복 할거야

138
00:07:37,490 --> 00:07:41,070
연결리스트의 전체
각 요소를 자유롭게.

139
00:07:41,070 --> 00:07:46,070
이제, 우리는 조심해야합니다, 그래서 여기에 우리
의 임시 변수가

140
00:07:46,070 --> 00:07:49,740
다음에 포인터를 저장
링크 된 목록의 요소입니다.

141
00:07:49,740 --> 00:07:52,140
그리고 우리는 자유에가는거야
현재 요소.

142
00:07:52,140 --> 00:07:55,990
>> 우리는 우리가 우리 때문에이 작업을 수행해야 할 필요가
다만 현재 요소에게 무료로 할 수

143
00:07:55,990 --> 00:07:59,260
다음 다음 포인터에 액세스하려고
이후 한 번 우리는 그것을 해제

144
00:07:59,260 --> 00:08:00,870
메모리는 무효가됩니다.

145
00:08:00,870 --> 00:08:04,990
그래서 우리는 포인터를 주위에 유지해야
다음 요소는, 우리가 확보 할 수 있습니다

146
00:08:04,990 --> 00:08:08,360
현재 요소, 그리고, 우리는 업데이트 할 수 있습니다
를 가리 키도록 현재의 요소

147
00:08:08,360 --> 00:08:09,590
다음 요소.

148
00:08:09,590 --> 00:08:12,770
>> 우리는 요소는 루프가 있습니다 동안
이 연결리스트에서.

149
00:08:12,770 --> 00:08:16,450
우리는 모든 연결된 목록을 위해 그렇게 할 것이다
해시 테이블, 그리고 우리가 완료 한

150
00:08:16,450 --> 00:08:20,180
그와 함께, 우리는 완전히 언로드했습니다
해시 테이블, 우리는 끝났어.

151
00:08:20,180 --> 00:08:24,050
그래서 언로드에 대한에 지금까지 불가능
false를 반환하고, 우리가 수행하고, 우리

152
00:08:24,050 --> 00:08:25,320
진실이 돌아갑니다.

153
00:08:25,320 --> 00:08:27,563