1
00:00:00,000 --> 00:00:00,500

2
00:00:00,500 --> 00:00:01,900
[음악 재생]

3
00:00:01,900 --> 00:00:05,710

4
00:00:05,710 --> 00:00:09,150
>> DOUG 로이드 : 지금 당신
배열에 대해 많이 알고,

5
00:00:09,150 --> 00:00:11,610
당신은 연결리스트에 대해 많이 알고있다.

6
00:00:11,610 --> 00:00:13,650
그리고 우리는 논의했습니다
장점과 단점, 우리가했습니다

7
00:00:13,650 --> 00:00:16,620
목록을 연결하는 논의
크고 작은 얻을 수 있습니다,

8
00:00:16,620 --> 00:00:18,630
하지만 그들은 더 많은 크기를 차지합니다.

9
00:00:18,630 --> 00:00:22,359
배열은 훨씬 더 간단한다
사용하지만, 그들은만큼에 제한있어

10
00:00:22,359 --> 00:00:24,900
우리는의 크기를 설정할 필요로
처음에 배열

11
00:00:24,900 --> 00:00:26,910
그리고 우리는 함께 붙어있어.

12
00:00:26,910 --> 00:00:30,470
>> 하지만 우리가 꽤 많이했습니다,의
우리의 모든 주제를 소진

13
00:00:30,470 --> 00:00:33,040
연결리스트와 배열에 대한.

14
00:00:33,040 --> 00:00:34,950
아니면 우리가 있나요?

15
00:00:34,950 --> 00:00:37,720
어쩌면 우리가 뭔가를 할 수
보다 창조적 인.

16
00:00:37,720 --> 00:00:40,950
그리고 준다 그런 종류의
해시 테이블의 개념.

17
00:00:40,950 --> 00:00:46,680
>> 그래서 해시 테이블에서 우리는 시도 할거야
연결리스트와 배열을 결합한다.

18
00:00:46,680 --> 00:00:49,520
우리는 이점을거야
어레이, 랜덤 액세스 등에

19
00:00:49,520 --> 00:00:53,510
그냥 배열에 갈 수있는
요소 (4) 또는 배열 요소 (8)

20
00:00:53,510 --> 00:00:55,560
에서 반복 할 필요없이.

21
00:00:55,560 --> 00:00:57,260
그건 바로, 꽤 빨리입니까?

22
00:00:57,260 --> 00:01:00,714
>> 그러나 우리는 또한 우리의 데이터를 갖고 싶어
구조는 성장하고 축소 할 수 있습니다.

23
00:01:00,714 --> 00:01:02,630
우리는 우리가하지 않는, 필요하지 않습니다
제한하려는.

24
00:01:02,630 --> 00:01:04,588
그리고 우리가 할 수 있도록하려면
추가하고 물건을 제거하는

25
00:01:04,588 --> 00:01:08,430
아주 쉽게, 어떤 당신이 기억하는 경우,
배열이 매우 복잡하다.

26
00:01:08,430 --> 00:01:11,650
그리고 우리는이를 호출 할 수 있습니다
새로운 것은 해시 테이블.

27
00:01:11,650 --> 00:01:15,190
>> 그리고 경우는, 올바르게 구현
우리는 일종의 취하고있어

28
00:01:15,190 --> 00:01:18,150
두 데이터의 장점
이미 본 적이 구조,

29
00:01:18,150 --> 00:01:19,880
배열과 연결리스트.

30
00:01:19,880 --> 00:01:23,070
삽입을 시작할 수 있습니다
1 세타쪽으로 경향이있다.

31
00:01:23,070 --> 00:01:26,207
세타 우리가 정말 논의하지 않은,
하지만 세타는 평균 경우입니다,

32
00:01:26,207 --> 00:01:27,540
무슨 일이 실제로 일어날 것입니다.

33
00:01:27,540 --> 00:01:29,680
당신은 항상 않을거야
최악의 시나리오를 가지고,

34
00:01:29,680 --> 00:01:32,555
그리고 당신은 항상 가지고 않을거야
최선의 시나리오는, 그래서이다

35
00:01:32,555 --> 00:01:33,900
평균 시나리오?

36
00:01:33,900 --> 00:01:36,500
>> 그럼 평균 삽입
해시 테이블에

37
00:01:36,500 --> 00:01:39,370
가까운 일정 시간에 얻을 시작할 수 있습니다.

38
00:01:39,370 --> 00:01:41,570
그리고 삭제 얻을 수 있습니다
일정 시간에 닫습니다.

39
00:01:41,570 --> 00:01:44,440
그리고 조회를 얻을 수 있습니다
일정 시간에 닫습니다.

40
00:01:44,440 --> 00:01:48,600
That's-- 우리는 데이터가 없습니다
구조는 아직 그 작업을 수행 할 수 있습니다,

41
00:01:48,600 --> 00:01:51,180
그래서이 이미 소리
꽤 좋은 점 등을들 수있다.

42
00:01:51,180 --> 00:01:57,010
우리는 정말 완화 한
그 자체로 각각의 단점.

43
00:01:57,010 --> 00:01:59,160
>> 이 성능을 얻으려면
하지만 우리를 업그레이드

44
00:01:59,160 --> 00:02:03,580
우리가 추가하는 방법을 재고 할 필요가
구조로 데이터.

45
00:02:03,580 --> 00:02:07,380
특히 우리가 원하는
데이터 자체는 우리에게

46
00:02:07,380 --> 00:02:09,725
어디는 구조로 가야한다.

47
00:02:09,725 --> 00:02:12,850
그리고 우리는이에 있다면 참조 할 필요가있는 경우
구조, 우리가 그것을 발견 할 필요가있는 경우,

48
00:02:12,850 --> 00:02:16,610
우리는 데이터를보고 싶어
다시하고 효과적으로 할 수 수

49
00:02:16,610 --> 00:02:18,910
데이터를 사용하여, 랜덤 액세스.

50
00:02:18,910 --> 00:02:20,700
그냥보고에 의해
데이터 우리는해야한다

51
00:02:20,700 --> 00:02:25,890
정확히 우리가있어 어디의 아이디어
해시 테이블에서 찾을 것.

52
00:02:25,890 --> 00:02:28,770
>> 해시 이제 단점
테이블은 정말 걸이다

53
00:02:28,770 --> 00:02:31,770
주문 또는 데이터를 정렬 꽤 나쁜.

54
00:02:31,770 --> 00:02:34,970
그리고 사실, 당신은 시작하는 경우
주문하거나 정렬을 사용하는

55
00:02:34,970 --> 00:02:37,990
데이터는 모두 손실
이점 이전에

56
00:02:37,990 --> 00:02:40,710
삽입과 삭제의 관점에서했다.

57
00:02:40,710 --> 00:02:44,060
시간에 가까워 질수록
N의 세타, 우리는 기본적했습니다

58
00:02:44,060 --> 00:02:45,530
연결리스트로 회귀.

59
00:02:45,530 --> 00:02:48,850
그래서 우리는 해시를 사용하려면
테이블 우리가 걱정하지 않는 경우

60
00:02:48,850 --> 00:02:51,490
데이터를 정렬되어 있는지 여부를 확인합니다.

61
00:02:51,490 --> 00:02:54,290
문맥있는
당신은 CS50에서 사용할 수 있습니다

62
00:02:54,290 --> 00:02:58,900
당신은 아마 상관 없어
데이터를 정렬된다.

63
00:02:58,900 --> 00:03:03,170
>> 그래서 해시 테이블의 조합이다
별개의 두 조각

64
00:03:03,170 --> 00:03:04,980
있는 우리는 잘 알고.

65
00:03:04,980 --> 00:03:07,930
첫 번째 함수 인
우리는 일반적으로 해시 함수를 호출합니다.

66
00:03:07,930 --> 00:03:11,760
그리고 해쉬 함수에 가고
일부 음이 아닌 정수를 반환하는

67
00:03:11,760 --> 00:03:14,870
우리는 일반적으로 확인, 해시 코드를 호출?

68
00:03:14,870 --> 00:03:20,230
두 번째 부분은 배열입니다
우리 형의 데이터 저장 능력

69
00:03:20,230 --> 00:03:22,190
데이터 구조로 배치 할.

70
00:03:22,190 --> 00:03:24,310
우리는에 보류합니다
지금은 목록 요소를 연결

71
00:03:24,310 --> 00:03:27,810
단지의 기초부터 시작
그것의 주위에 당신의 머리를 얻기 위해 테이블​​을 해시,

72
00:03:27,810 --> 00:03:30,210
그리고, 우리는 아마 타격 것
당신의 마음을 조금 때

73
00:03:30,210 --> 00:03:32,920
함께 배열과 링크 목록을 결합한다.

74
00:03:32,920 --> 00:03:35,590
>> 기본적인 생각하지만
우리는 일부 데이터를 가지고 있습니다.

75
00:03:35,590 --> 00:03:37,860
우리는 데이터를 통해 실행
해시 함수.

76
00:03:37,860 --> 00:03:41,980
그리고 데이터 처리
그것은 확인 번호를 뱉어?

77
00:03:41,980 --> 00:03:44,890
그리고 그 수와
우리는 단지 데이터를 저장

78
00:03:44,890 --> 00:03:48,930
우리는에 저장할
그 위치에 배열입니다.

79
00:03:48,930 --> 00:03:53,990
그래서 예를 들어 우리는 어쩌면이
문자열의 해시 테이블.

80
00:03:53,990 --> 00:03:57,350
그것은 그래서, 10 요소를 가지고
우리는 10 문자열에 맞게 할 수 있습니다.

81
00:03:57,350 --> 00:03:59,320
>> 이제 우리는 존 해시하려는 가정 해 봅시다.

82
00:03:59,320 --> 00:04:02,979
존 그래서 데이터로 우리는 삽입 할
어딘가에이 해시 테이블에.

83
00:04:02,979 --> 00:04:03,770
우리는 어디를 배치해야합니까?

84
00:04:03,770 --> 00:04:05,728
그런데 일반적으로
배열 지금까지 우리는 아마

85
00:04:05,728 --> 00:04:07,610
배열 위치 0에 넣어 것입니다.

86
00:04:07,610 --> 00:04:09,960
하지만 지금 우리는이 새로운 해시 함수를 가지고있다.

87
00:04:09,960 --> 00:04:13,180
>> 그리고 이제 우리는 존을 실행한다고 가정 해 봅시다
이 해시 함수를 통해

88
00:04:13,180 --> 00:04:15,417
그리고 4 뱉어입니다.

89
00:04:15,417 --> 00:04:17,500
우린 여기서 뭐 그건
존을 데려 가고 싶다는 것.

90
00:04:17,500 --> 00:04:22,050
우리는 배열 위치에 존을 데려 가고 싶다는
4, 우리는 again-- 존 해시 경우 때문에

91
00:04:22,050 --> 00:04:23,810
의 나중에에게 우리 말을하자
검색 및보고 싶어

92
00:04:23,810 --> 00:04:26,960
요한은이 해시에있는 경우
우리가해야 할 모든 table--

93
00:04:26,960 --> 00:04:30,310
동일한 해시를 통해 실행
기능, 숫자 4 점을 얻을

94
00:04:30,310 --> 00:04:33,929
존을 찾​​을 수
바로 우리의 데이터 구조.

95
00:04:33,929 --> 00:04:34,720
그건 꽤 좋은입니다.

96
00:04:34,720 --> 00:04:36,928
>> 의 우리가 지금 이렇게 가정 해 봅시다
다시, 우리는 바울을 해시하고 싶다.

97
00:04:36,928 --> 00:04:39,446
우리는 바울을 추가 할
이 해시 테이블에.

98
00:04:39,446 --> 00:04:42,070
의이 시간은 우리가 실행한다고 가정 해 봅시다
해쉬 함수를 통해 폴

99
00:04:42,070 --> 00:04:44,600
생성 된 해시 코드는 6입니다.

100
00:04:44,600 --> 00:04:47,340
그런데 지금 우리는 바울을 넣을 수 있습니다
어레이 위치 6.

101
00:04:47,340 --> 00:04:50,040
그리고 우리는 여부를 조회 할 필요가있는 경우
폴이 해시 테이블 인,

102
00:04:50,040 --> 00:04:53,900
우리가해야 할 모든 폴 실행
해쉬 함수를 통해 다시

103
00:04:53,900 --> 00:04:55,830
우리는 밖으로 다시 6을 얻을 것입니다.

104
00:04:55,830 --> 00:04:57,590
>> 그리고 우리는 단지보고
배열 위치 (6)에서.

105
00:04:57,590 --> 00:04:58,910
바울이 있습니까?

106
00:04:58,910 --> 00:05:00,160
그렇다면, 그는 해시 테이블에 있습니다.

107
00:05:00,160 --> 00:05:01,875
바울은하지 있습니까?

108
00:05:01,875 --> 00:05:03,000
그는 해시 테이블에없는.

109
00:05:03,000 --> 00:05:05,720
그것은 매우 간단합니다.

110
00:05:05,720 --> 00:05:07,770
>> 이제 당신은 어떻게 해시 함수를 정의 할 수 있습니까?

111
00:05:07,770 --> 00:05:11,460
그럼 정말 제한이 없습니다
가능한 해쉬 함수의 수입니다.

112
00:05:11,460 --> 00:05:14,350
사실의 수는, 거기에 정말
인터넷에 정말 좋은 것.

113
00:05:14,350 --> 00:05:17,560
의 수는 정말로있다
인터넷에 정말 나쁜 사람.

114
00:05:17,560 --> 00:05:21,080
그것은 또한 아주 쉽게
나쁜 하나를 작성합니다.

115
00:05:21,080 --> 00:05:23,760
>> 그래서 좋은를 구성하는
해시 기능, 오른쪽?

116
00:05:23,760 --> 00:05:27,280
그럼 좋은 해시 함수는해야
데이터 만이 사용되는 해시,

117
00:05:27,280 --> 00:05:29,420
및 데이터의 모든 해시된다.

118
00:05:29,420 --> 00:05:32,500
그래서 우리는 anything-- 사용하지 않으려는
우리는 아무것도 포함하지 않는다

119
00:05:32,500 --> 00:05:35,560
데이터 이외의 다른.

120
00:05:35,560 --> 00:05:37,080
우리는 모든 데이터를 사용할.

121
00:05:37,080 --> 00:05:39,830
우리는 단지 한 조각을 사용하지 않으
그것을, 우리는 모두 사용하고 싶습니다.

122
00:05:39,830 --> 00:05:41,710
해시 함수해야
또한 결정합니다.

123
00:05:41,710 --> 00:05:42,550
그게 무슨 뜻 이죠?

124
00:05:42,550 --> 00:05:46,200
잘 그것은 즉, 때마다 우리
데이터의 동일한 부분을 통과

125
00:05:46,200 --> 00:05:50,040
해시 함수로 우리 항상
같은 해시 코드를 얻을.

126
00:05:50,040 --> 00:05:52,870
나는에 존을 통과하는 경우
해시 함수는 내가 4를 얻는다.

127
00:05:52,870 --> 00:05:56,110
나는 그렇게 할 수 있어야한다 10,000
시간과 나는 항상 4를 얻을 수 있습니다.

128
00:05:56,110 --> 00:06:00,810
그래서 임의의 숫자를 효과적으로
우리의 해시에 관여 할 수 tables--

129
00:06:00,810 --> 00:06:02,750
우리의 해시 함수에.

130
00:06:02,750 --> 00:06:05,750
>> 해시 함수는해야
균일하게 데이터를 배포 할 수 있습니다.

131
00:06:05,750 --> 00:06:09,700
때마다 당신은을 통해 데이터를 실행하는 경우
해시 함수는, 해시 코드 0을 얻을

132
00:06:09,700 --> 00:06:11,200
맞아, 아마 그렇게 큰 아니에요?

133
00:06:11,200 --> 00:06:14,600
당신은 아마 큰 원하는
해시 코드의 범위.

134
00:06:14,600 --> 00:06:17,190
또한 일이 확산 될 수
테이블을 통해 밖으로.

135
00:06:17,190 --> 00:06:23,210
또한이 경우에 정말 좋은 것
존과 요나단 같은 유사한 데이터,

136
00:06:23,210 --> 00:06:26,320
아마 무게를 확산했다
해시 테이블의 다른 위치.

137
00:06:26,320 --> 00:06:28,750
즉 좋은 장점이 될 것입니다.

138
00:06:28,750 --> 00:06:31,250
>> 다음은 해시 함수의 예입니다.

139
00:06:31,250 --> 00:06:33,150
나는 이번 일을 썼다.

140
00:06:33,150 --> 00:06:35,047
그것은 특히 아니다
좋은 해시 함수

141
00:06:35,047 --> 00:06:37,380
정말하지 않는 이유
지금에가는 부담.

142
00:06:37,380 --> 00:06:41,040
하지만 당신은 여기 무슨 일이야 볼 수 있습니까?

143
00:06:41,040 --> 00:06:44,420
우리는 변수를 선언하는 것 같다
합과 0이 그것을 설정했다.

144
00:06:44,420 --> 00:06:50,010
그리고 분명히 내가 뭔가를하고 있어요
너무 오래 strstr과 [J]가 동일하지 않은 것처럼

145
00:06:50,010 --> 00:06:52,490
0 백 슬래시합니다.

146
00:06:52,490 --> 00:06:54,870
내가 거기 뭐하는 거지?

147
00:06:54,870 --> 00:06:57,440
>> 이것은 기본적으로 또 다른입니다
[을 구현하는 방법은? strl?]

148
00:06:57,440 --> 00:06:59,773
당신이했습니다 때 검출
문자열의 끝에 도달.

149
00:06:59,773 --> 00:07:02,480
그래서 사실 필요가 없습니다
문자열의 길이를 계산

150
00:07:02,480 --> 00:07:05,640
나는를 쳤을 때 그냥 사용하고 있습니다
백 슬래시 0 문자 내가 아는

151
00:07:05,640 --> 00:07:07,185
나는 문자열의 끝에 도달했습니다.

152
00:07:07,185 --> 00:07:09,560
그리고 나는 계속거야
해당 문자열을 반복,

153
00:07:09,560 --> 00:07:15,310
strstr과 [J]를 추가하면에서 다음 합계,하고
하루의 끝은 합계 모드를 반환하는 것

154
00:07:15,310 --> 00:07:16,200
HASH_MAX.

155
00:07:16,200 --> 00:07:18,700
>> 기본적으로이 모든 해시
기능까지 추가하고하고있다

156
00:07:18,700 --> 00:07:23,450
의 ASCII 값의 모든
내 문자열은 다음 그건

157
00:07:23,450 --> 00:07:26,390
일부 해시 코드를 반환
HASH_MAX에 의해 modded하게.

158
00:07:26,390 --> 00:07:29,790
아마 크기의
내 배열의 오른쪽?

159
00:07:29,790 --> 00:07:33,160
나는 해시를 받고 싶지 않아
코드 내 배열의 사이즈가 10 인 경우,

160
00:07:33,160 --> 00:07:35,712
나는지고 ​​싶지 않아
아웃 해시 코드 11, 12,

161
00:07:35,712 --> 00:07:38,690
13, 나는에 물건을 넣을 수 없습니다
그 어레이의 위치,

162
00:07:38,690 --> 00:07:39,790
그 불법이 될 것이다.

163
00:07:39,790 --> 00:07:42,130
나는 세그먼트 오류 고통을 것입니다.

164
00:07:42,130 --> 00:07:45,230
>> 이제 여기에 또 다른 빠른 옆입니다.

165
00:07:45,230 --> 00:07:48,470
일반적으로 당신은 아마하지 않을거야
자신의 해시 함수를 작성하려고합니다.

166
00:07:48,470 --> 00:07:50,997
실제로 약간입니다
예술이 아니라 과학입니다.

167
00:07:50,997 --> 00:07:52,580
그리고 그들로가는 많은있다.

168
00:07:52,580 --> 00:07:55,288
내가 말한 것처럼 인터넷은, 가득
정말 좋은 해시 함수,

169
00:07:55,288 --> 00:07:58,470
당신은 인터넷을 사용해야합니다
정말 때문에 해시 함수를 찾을 수

170
00:07:58,470 --> 00:08:03,230
단지 종류의 필요를
시간의 낭비는 자신을 만들 수 있습니다.

171
00:08:03,230 --> 00:08:05,490
>> 당신은 간단한 것들을 쓸 수 있습니다
테스트 목적.

172
00:08:05,490 --> 00:08:08,323
그러나 실제로하려고 할 때는
데이터를 해싱하고 저장 시작

173
00:08:08,323 --> 00:08:10,780
당신이있어 해시 테이블에
아마 할 것

174
00:08:10,780 --> 00:08:14,580
생성 된 일부 기능을 사용
당신을 위해, 그 인터넷에 존재합니다.

175
00:08:14,580 --> 00:08:17,240
당신은 확신 할 경우
당신의 소스를 인용합니다.

176
00:08:17,240 --> 00:08:21,740
이유에가 없습니다
여기에 아무것도 표절.

177
00:08:21,740 --> 00:08:25,370
>> 컴퓨터 과학 커뮤니티입니다
확실히 값을 성장, 정말

178
00:08:25,370 --> 00:08:28,796
오픈 소스, 그리고 정말 중요합니다
당신의 소스를 인용 할 수 있도록 사람들

179
00:08:28,796 --> 00:08:30,670
에 대한 속성을 얻을 수 있습니다
그들이있어 작업

180
00:08:30,670 --> 00:08:32,312
지역 사회의 이익을 위해 일을.

181
00:08:32,312 --> 00:08:34,020
그래서 항상 sure-- 수
뿐 아니라 해시에 대한

182
00:08:34,020 --> 00:08:37,270
기능, 그러나 일반적으로 때를
외부 소스 코드를 사용,

183
00:08:37,270 --> 00:08:38,299
항상 당신의 소스를 인용.

184
00:08:38,299 --> 00:08:43,500
한 사람에게 신용을 줘
작품의 일부는 그래서 당신은 할 필요가 없습니다.

185
00:08:43,500 --> 00:08:46,720
>> 확인 그래서이를 다시 방문하자
두 번째 해시 테이블.

186
00:08:46,720 --> 00:08:48,780
우리가 떠나기 곳이다
우리가 삽입 된 후 해제

187
00:08:48,780 --> 00:08:53,300
이 해시 테이블에 존과 폴.

188
00:08:53,300 --> 00:08:55,180
여기서 문제를 볼 수 있습니까?

189
00:08:55,180 --> 00:08:58,410
두 가지를 볼 수 있습니다.

190
00:08:58,410 --> 00:09:02,240
그러나 특히, 당신을
이 가능한 문제를 볼?

191
00:09:02,240 --> 00:09:06,770
>> 나는 무엇 링고 해시하고있는 경우
후 처리 밝혀

192
00:09:06,770 --> 00:09:14,000
해쉬 함수를 통해 데이터
링고는 해시 코드 (6)를 생성합니다.

193
00:09:14,000 --> 00:09:16,810
이미 데이터를 가지고
hashcode-- 배열 위치 (6).

194
00:09:16,810 --> 00:09:22,000
그래서 아마 조금 될 것
지금 나에게 문제가, 오른쪽?

195
00:09:22,000 --> 00:09:23,060
>> 우리는 충돌이를 호출합니다.

196
00:09:23,060 --> 00:09:26,460
및 충돌시 발생하는 두
데이터의 조각들은 동일한 해시를 통해 실행할

197
00:09:26,460 --> 00:09:29,200
함수는 동일한 해시를 산출.

198
00:09:29,200 --> 00:09:32,850
아마도 우리는 여전히 모두 싶어
해시 테이블로 데이터 조각

199
00:09:32,850 --> 00:09:36,330
그렇지 않으면 우리는 링고가 실행되지 않을 것이다
임의로 해쉬 함수를 통한.

200
00:09:36,330 --> 00:09:40,870
우리는 아마도 싶어
그 배열에 링고.

201
00:09:40,870 --> 00:09:46,070
>> 우리가 비록 그것을 어떻게, 그는 경우
바울 모두 수율 해시 코드 (6)?

202
00:09:46,070 --> 00:09:49,520
우리는 바울을 덮어 싶지 않아,
우리는 바울이 너무가되고 싶어요.

203
00:09:49,520 --> 00:09:52,790
그래서 우리가 얻을 수있는 방법을 찾을 필요
해시 테이블에 요소가

204
00:09:52,790 --> 00:09:56,550
여전히 우리의 빠른을 유지
삽입 및 훑어보기까지.

205
00:09:56,550 --> 00:10:01,350
그리고 그것을 처리하는 한 가지 방법은이다
프로빙 선형라는 뭔가.

206
00:10:01,350 --> 00:10:04,170
>> 우리가있는 경우이 방법을 사용하여
충돌, 잘, 우리는 무엇을해야합니까?

207
00:10:04,170 --> 00:10:08,580
그런데 우리는 배열 위치에 그를 넣어 수 없습니다
6, 또는 어떤 해시 코드 생성,

208
00:10:08,580 --> 00:10:10,820
의는 해시 플러스 1에 집어 넣어 보자.

209
00:10:10,820 --> 00:10:13,670
그리고 전체하자의 경우
해시 플러스 2에서 그를 넣어.

210
00:10:13,670 --> 00:10:17,420
이 존재의 장점 그는 있다면
정확히 우리는 그가 생각하는 경우,

211
00:10:17,420 --> 00:10:20,850
우리는 검색을 시작해야한다,
어쩌면 우리는 너무 멀리 갈 필요가 없습니다.

212
00:10:20,850 --> 00:10:23,900
어쩌면 우리는 검색하지 않아도
해시 테이블의 모든 N 개의 소자.

213
00:10:23,900 --> 00:10:25,790
어쩌면 우리는 검색해야
그 중 몇 가지.

214
00:10:25,790 --> 00:10:30,680
>> 그래서 우리는 여전히쪽으로 경향이있어
평균 경우는 1에 가까운 대 인 것을

215
00:10:30,680 --> 00:10:34,280
N에 가까운, 그래서 아마 그 작동합니다.

216
00:10:34,280 --> 00:10:38,010
그럼 방법이를 보자
현실에서 작동 할 수 있습니다.

217
00:10:38,010 --> 00:10:41,460
그리고 어쩌면 우리가 감지 할 수 있는지 보자
여기에 발생할 수있는 문제.

218
00:10:41,460 --> 00:10:42,540
>> 의 우리가 바트 해시 가정 해 봅시다.

219
00:10:42,540 --> 00:10:45,581
그래서 지금 우리는 새로운 설정을 실행하는거야
해쉬 함수를 통해 문자열,

220
00:10:45,581 --> 00:10:48,460
우리는 해시를 통해 바트를 실행
기능, 우리는 해시 코드 (6)을 얻는다.

221
00:10:48,460 --> 00:10:52,100
우리는 좀 봐, 우리는 6가 참조
빈, 그래서 우리가 바트를 넣을 수 있습니다.

222
00:10:52,100 --> 00:10:55,410
>> 이제 우리는 리사와 그 해시
또한 해시 코드 (6)를 생성한다.

223
00:10:55,410 --> 00:10:58,330
그런데 지금 우리는이를 사용하고 있는지
선형, 우리는 6시에 시작하는 방법을 프로빙

224
00:10:58,330 --> 00:10:59,330
우리는 6가 가득 것을 알 수있다.

225
00:10:59,330 --> 00:11:00,990
우리는 6 리사를 넣을 수 없습니다.

226
00:11:00,990 --> 00:11:02,090
그래서 우리는 어디에 가야합니까?

227
00:11:02,090 --> 00:11:03,280
의 7에 가자.

228
00:11:03,280 --> 00:11:04,610
(7)의 빈, 그래서 작품을.

229
00:11:04,610 --> 00:11:06,510
그래서이 리사를 만들어 보자.

230
00:11:06,510 --> 00:11:10,200
>> 이제 우리는 호머 해시 우리는 7 얻을.

231
00:11:10,200 --> 00:11:13,380
확인을 잘 우리는 알고있다 (7)의 전체가
지금, 우리가 호머를 넣을 수 없습니다.

232
00:11:13,380 --> 00:11:14,850
그럼 8로 가자.

233
00:11:14,850 --> 00:11:15,664
8은 사용할 수 있습니까?

234
00:11:15,664 --> 00:11:18,330
그래, 그리고 7 ~ 8의 가까운, 그래서 경우
우리는 우리가있어 검색을 시작해야

235
00:11:18,330 --> 00:11:20,020
너무 멀리 갈 필요하지 않을.

236
00:11:20,020 --> 00:11:22,860
그래서의 8에서 호머을 만들어 보자.

237
00:11:22,860 --> 00:11:25,151
>> 이제 우리는 해시 매기와
3 반환, 선 (善) 감사합니다

238
00:11:25,151 --> 00:11:26,650
우리는 단지이 매기를 넣을 수있어.

239
00:11:26,650 --> 00:11:29,070
우리는 어떤 작업을 수행 할 필요가 없습니다
종류의 프로빙.

240
00:11:29,070 --> 00:11:32,000
이제 우리는 마지 해시하고,
마지는 6을 반환합니다.

241
00:11:32,000 --> 00:11:39,560
>> 그럼 6, 8이 가득, 7가 가득, 가득
9, 모든 권리 (9)가 비어있는, 하나님 께 감사를드립니다.

242
00:11:39,560 --> 00:11:41,600
나는 9시에 마지를 넣을 수 있습니다.

243
00:11:41,600 --> 00:11:45,280
이미 우리는 우리가 시작하는 것을 볼 수있다
우린 지금이 문제가있는

244
00:11:45,280 --> 00:11:48,780
종류의 일을 스트레칭하기 시작
의 멀리 자신의 해시 코드에서.

245
00:11:48,780 --> 00:11:52,960
그리고 1의 세타, 그 평균
일정 시간 인 경우,

246
00:11:52,960 --> 00:11:56,560
조금 more--를 얻을 시작
더 작은 경향 시작

247
00:11:56,560 --> 00:11:58,050
N의 세타으로.

248
00:11:58,050 --> 00:12:01,270
우리는을 잃게하기 시작하고
해시 테이블을 이용.

249
00:12:01,270 --> 00:12:03,902
>> 우리가 방금 본이 문제
클러스터링이라고 무언가이다.

250
00:12:03,902 --> 00:12:06,360
그리고 정말 나쁜거야
클러스터링은 당신이 한 번 지금

251
00:12:06,360 --> 00:12:09,606
측면 두 가지 요소에 의해이
그것은 더욱 가능성있게 좌우,

252
00:12:09,606 --> 00:12:11,480
당신은 두 번이
기회는거야

253
00:12:11,480 --> 00:12:13,516
또 다른 충돌을 갖도록
해당 클러스터와,

254
00:12:13,516 --> 00:12:14,890
클러스터는 하나 성장할 것이다.

255
00:12:14,890 --> 00:12:19,640
그리고 당신은 성장하고 성장하겠습니다
충돌을 가진 당신의 가능성.

256
00:12:19,640 --> 00:12:24,470
그리고 결국은 그냥 나쁜
같은 모든 데이터를 정렬하지.

257
00:12:24,470 --> 00:12:27,590
>> 다른 문제는 비록 우리입니다
아직도, 지금까지 지금까지,

258
00:12:27,590 --> 00:12:30,336
우리는 그저 봤는데
해시 테이블을 손쉽게 이해

259
00:12:30,336 --> 00:12:31,960
우리는 여전히 10 문자열을위한 공간을 가지고있다.

260
00:12:31,960 --> 00:12:37,030
우리는 해시를 계속하려면
스프링 필드의 시민,

261
00:12:37,030 --> 00:12:38,790
우리는 거기에 그들 중 (10)를 얻을 수 있습니다.

262
00:12:38,790 --> 00:12:42,619
그리고 우리는 시도하고 11 일 또는 12 일을 추가하는 경우
우리는 그들을 놓을 곳이 없습니다.

263
00:12:42,619 --> 00:12:45,660
우리는 주변에서 회전 될 수있다
원 빈 자리를 찾기 위해 노력

264
00:12:45,660 --> 00:12:49,000
우리는 어쩌면 박히
무한 루프에.

265
00:12:49,000 --> 00:12:51,810
>> 그래서 아이디어를 빌려 이런 종류의
뭔가 체인했다.

266
00:12:51,810 --> 00:12:55,790
그리고 이것은 우리가 가지고가는 곳이다
다시 그림으로 연결리스트.

267
00:12:55,790 --> 00:13:01,300
어떤 경우 대신 저장
어레이 내의 데이터 자체

268
00:13:01,300 --> 00:13:04,471
배열의 모든 요소 수
여러 개의 데이터를 보유?

269
00:13:04,471 --> 00:13:05,970
잘 맞아, 이해가되지 않습니다?

270
00:13:05,970 --> 00:13:09,280
우리는 그 배열 만 할 수있는 알고
배열의 각 요소를 잠시,

271
00:13:09,280 --> 00:13:12,930
하나의 조각을 보유 할 수 있습니다
데이터 타입의 데이터.

272
00:13:12,930 --> 00:13:16,750
>> 하지만 경우 해당 데이터 유형
연결리스트, 오른쪽입니까?

273
00:13:16,750 --> 00:13:19,830
그래서 만약에 모든
배열의 요소였다

274
00:13:19,830 --> 00:13:22,790
연결리스트의 헤드 포인터?

275
00:13:22,790 --> 00:13:24,680
그리고 우리는 만들 수
그 연결리스트

276
00:13:24,680 --> 00:13:27,120
및 임의로 그들을 성장
연결리스트가 수 있기 때문에

277
00:13:27,120 --> 00:13:32,090
우리는 성장하고 더 많은 축소하는
배열을 수행 유연보다.

278
00:13:32,090 --> 00:13:34,210
그래서 우리가 지금 사용하는 경우,
우리는 바로이 활용?

279
00:13:34,210 --> 00:13:37,760
우리는이 사슬을 성장 시작
이러한 배열 위치가 부족합니다.

280
00:13:37,760 --> 00:13:40,740
>> 이제 우리는 무한에 맞게 수
데이터의 양, 또는 무한하지

281
00:13:40,740 --> 00:13:44,170
임의의 양
데이터, 우리의 해시 테이블에

282
00:13:44,170 --> 00:13:47,760
적으로 실행하지 않고
충돌의 문제.

283
00:13:47,760 --> 00:13:50,740
우리는 또한 제거했습니다
이렇게하면 클러스터링.

284
00:13:50,740 --> 00:13:54,380
그리고 물론 우리는 우리가 삽입 할 때 알고
연결리스트로, 당신이 기억하는 경우

285
00:13:54,380 --> 00:13:57,779
단독으로, 연결리스트에 우리의 비디오에서
연결리스트와 이중 연결리스트,

286
00:13:57,779 --> 00:13:59,070
이는 일정 시간 운전이다.

287
00:13:59,070 --> 00:14:00,710
우리는 단지 전면에 추가하고 있습니다.

288
00:14:00,710 --> 00:14:04,400
>> 그리고 모양까지에 대해 잘 우리는 알고있다
즉, 연결리스트에서 찾아 볼

289
00:14:04,400 --> 00:14:05,785
바로, 문제가 될 수있다?

290
00:14:05,785 --> 00:14:07,910
우리는을 통해 검색 할 수있다
처음부터 끝까지.

291
00:14:07,910 --> 00:14:10,460
더 무작위가 없습니다
링크 된 목록에 액세스 할 수 있습니다.

292
00:14:10,460 --> 00:14:15,610
그러나 경우 대신 하나를 갖는의 연결
조회 N 아 것 목록,

293
00:14:15,610 --> 00:14:19,590
우리는 지금 10 연결리스트를 가지고,
1,000 연결리스트,

294
00:14:19,590 --> 00:14:24,120
지금은 10로 나눈 N의 O이야,
또는 n의 O를 1000으로 나눈 값.

295
00:14:24,120 --> 00:14:26,940
>> 그리고 우리가 이야기하는 동안
이론적으로 복잡성에 대한

296
00:14:26,940 --> 00:14:30,061
우리는 실시간으로, 상수를 무시
이러한 일들이 실제로 문제가 세계,

297
00:14:30,061 --> 00:14:30,560
권리?

298
00:14:30,560 --> 00:14:33,080
우리는 실제로 알
이런 그

299
00:14:33,080 --> 00:14:36,610
10 배 빠른를 실행하려면,
1,000 배 빠른 속도로,

300
00:14:36,610 --> 00:14:41,570
우리는 긴 하나를 배포하고 있기 때문에
1000 작은 체인에서 체인.

301
00:14:41,570 --> 00:14:45,090
그래서 우리가 때마다 검색 할
우리가 할 수있는 그 체인 중 하나를 통해

302
00:14:45,090 --> 00:14:50,290
우리가 상관 없어 999 체인을 무시
약, 단지 그 하나를 검색 할 수 있습니다.

303
00:14:50,290 --> 00:14:53,220
>> 어떤에 평균에
1,000 시간이 짧아.

304
00:14:53,220 --> 00:14:56,460
그래서 우리는 여전히 일종의 있습니다
이 경우 평균쪽으로 경향

305
00:14:56,460 --> 00:15:01,610
일정 시간이되고 있지만,
단지 우리가 활용되기 때문에

306
00:15:01,610 --> 00:15:03,730
몇 가지 큰 상수 요소로 나누어.

307
00:15:03,730 --> 00:15:05,804
방법이 수도 보자
실제로 그래도 봐.

308
00:15:05,804 --> 00:15:08,720
그래서 이것은 우리가 가진 해시 테이블이었다
우리는 해시 테이블을 선언하기 전에

309
00:15:08,720 --> 00:15:10,270
문자열 (10)을 저장할 수 있었다.

310
00:15:10,270 --> 00:15:11,728
우리는 더 이상 그렇게하지 ​​않을거야.

311
00:15:11,728 --> 00:15:13,880
우리는 이미 알고있는
그 방법의 한계.

312
00:15:13,880 --> 00:15:20,170
이제 우리의 해시 테이블 될 것
노드 (10), 포인터 배열

313
00:15:20,170 --> 00:15:22,120
연결리스트의 머리에.

314
00:15:22,120 --> 00:15:23,830
>> 그리고 지금은 널 (null)입니다.

315
00:15:23,830 --> 00:15:26,170
그 10 포인터의 각각은 null입니다.

316
00:15:26,170 --> 00:15:29,870
아무것도 우리에 없다
지금 테이블을 해시.

317
00:15:29,870 --> 00:15:32,690
>> 이제 몇 가지를 넣어 시작하자
이 해시 테이블에 일.

318
00:15:32,690 --> 00:15:35,440
그리고의는이 방법이 얼마나 보자
우리에게 약간의 혜택을 누릴 것.

319
00:15:35,440 --> 00:15:36,760
의 지금 조이 해시 보자.

320
00:15:36,760 --> 00:15:40,210
우리는 문자열 조이를 통해 실행됩니다거야
해시 함수 우리는 6을 반환합니다.

321
00:15:40,210 --> 00:15:41,200
그런데 우리는 지금 무엇을해야합니까?

322
00:15:41,200 --> 00:15:44,090
>> 글쎄 지금은 연결리스트와 협력,
우리는 배열 작동하지 않는 것입니다.

323
00:15:44,090 --> 00:15:45,881
그리고 우리는 작업 할 때
연결리스트와 우리

324
00:15:45,881 --> 00:15:49,790
우리는 동적으로 시작해야합니다 알고
공간과 건물 체인을 할당하는 단계를 포함한다.

325
00:15:49,790 --> 00:15:54,020
즉 일종의 그 핵심이다 how--이다
연결리스트를 구축하는 요소.

326
00:15:54,020 --> 00:15:57,670
그래서 동적으로하자
조이위한 공간을 할당,

327
00:15:57,670 --> 00:16:00,390
다음의 체인에 그를 추가 할 수 있습니다.

328
00:16:00,390 --> 00:16:03,170
>> 그래서 지금 우리가 무슨 짓을했는지 봐.

329
00:16:03,170 --> 00:16:06,440
우리가 조이 해시 때 우리는 해시 코드 (6)을 얻었다.

330
00:16:06,440 --> 00:16:11,790
배열 위치 6에서 이제 포인터
연결리스트의 머리를 가리키는,

331
00:16:11,790 --> 00:16:14,900
그리고 지금은 만이다
연결리스트의 요소입니다.

332
00:16:14,900 --> 00:16:18,350
그리고 그 노드에서
연결리스트는 조이입니다.

333
00:16:18,350 --> 00:16:22,300
>> 우리가 조이를 볼 필요가 있다면
이후, 우리는 다시 조이 해시,

334
00:16:22,300 --> 00:16:26,300
우리는 우리를하기 때문에 다시 6을 얻을
해시 함수는 결정적이다.

335
00:16:26,300 --> 00:16:30,400
그리고 우리는 머리에서 시작
연결리스트의 지적

336
00:16:30,400 --> 00:16:33,360
배열 위치에 의해
6, 우리는 반복 할 수

337
00:16:33,360 --> 00:16:35,650
조이를 찾기 위해 노력하고 그 맞은 편.

338
00:16:35,650 --> 00:16:37,780
그리고 우리는 만들 경우 우리의
효과적으로 테이블을 해시,

339
00:16:37,780 --> 00:16:41,790
우리의 해시 함수를 효과적으로
물론 데이터를 배포하고,

340
00:16:41,790 --> 00:16:45,770
평균 이들 각각 연결된
모든 어레이 위치리스트

341
00:16:45,770 --> 00:16:50,110
경우의 크기 1/10 일 것이다 우리
단지 하나의 거대한로했다

342
00:16:50,110 --> 00:16:51,650
그것의 모든 링크 된 목록입니다.

343
00:16:51,650 --> 00:16:55,670
>> 우리는 거대한 연결된 것을 배포하는 경우
(10) 연결리스트에서리스트

344
00:16:55,670 --> 00:16:57,760
각 목록은 1/10 크기가됩니다.

345
00:16:57,760 --> 00:17:01,432
그리고 이렇게 10 배 빠른
를 통해 검색 할 수 있습니다.

346
00:17:01,432 --> 00:17:02,390
그래서 다시이 작업을 수행 할 수 있습니다.

347
00:17:02,390 --> 00:17:04,290
의 지금 로스 해시 보자.

348
00:17:04,290 --> 00:17:07,540
>> 그리고 이제 우리가 그렇게 할 때 로스를 가정 해 봅시다
우리가 얻을 해시 코드는 2입니다.

349
00:17:07,540 --> 00:17:10,630
그럼 이제 우리는 동적으로 할당
새로운 노드, 우리는 그 노드의 로스를 넣어

350
00:17:10,630 --> 00:17:14,900
우리는 배열 위치 지금 말
2, null로 가리키는 대신,

351
00:17:14,900 --> 00:17:18,579
링크의 머리를 가리키는
그의 유일한 노드 목록은 로스입니다.

352
00:17:18,579 --> 00:17:22,660
그리고 우리는, 우리를이 한 번 더 할 수
레이첼 해시 및 해시 코드 4를 얻을 수 있습니다.

353
00:17:22,660 --> 00:17:25,490
에 레이첼을 넣어, 새 노드를 MALLOC
노드 및 배열 위치를 말한다

354
00:17:25,490 --> 00:17:27,839
4 이제 머리를 가리키는
그 연결리스트의

355
00:17:27,839 --> 00:17:31,420
유일한 요소는 레이첼 될 일이.

356
00:17:31,420 --> 00:17:33,470
>> 확인을하지만이 경우 발생
우리는 충돌이?

357
00:17:33,470 --> 00:17:38,560
의 우리가 충돌을 처리하는 방법을 살펴 보자
별도의 체인 방법을 사용.

358
00:17:38,560 --> 00:17:39,800
의 피비 해시 보자.

359
00:17:39,800 --> 00:17:41,094
우리는 해시 코드 (6)을 얻는다.

360
00:17:41,094 --> 00:17:44,010
앞의 예에서 우리는 단지 있었다
배열의 문자열을 저장하는 단계를 포함한다.

361
00:17:44,010 --> 00:17:45,980
이 문제였다.

362
00:17:45,980 --> 00:17:48,444
>> 우리는 소지품 싶지 않아
조이, 우리는 이미했습니다

363
00:17:48,444 --> 00:17:51,110
우리는 약간의 클러스터링을 얻을 수 있음을 알
문제 우리가 시도하는 경우 단계

364
00:17:51,110 --> 00:17:52,202
통해 프로브.

365
00:17:52,202 --> 00:17:54,660
그러나 만약 우리가 그냥 가지
이 바로, 같은 방법으로 치료?

366
00:17:54,660 --> 00:17:57,440
그냥 요소를 추가처럼
연결리스트의 머리에.

367
00:17:57,440 --> 00:18:00,220
피비 용의 단지 malloc에​​ 공간을 보자.

368
00:18:00,220 --> 00:18:04,764
>> 우리는 피비의 다음 포인터 점을 말할 것
연결리스트의 이전 머리에,

369
00:18:04,764 --> 00:18:07,180
다음 6 단지를 가리키는
연결리스트의 새로운 머리.

370
00:18:07,180 --> 00:18:10,150
그리고 지금 우리의 피비를 변경 한 봐.

371
00:18:10,150 --> 00:18:14,210
우리는 지금 두 가지를 저장할 수 있습니다
해시 코드 6 요소,

372
00:18:14,210 --> 00:18:17,170
우리는 어떤 문제가 발생하지 않습니다.

373
00:18:17,170 --> 00:18:20,147
>> 즉, 거의 전부
체인에있다.

374
00:18:20,147 --> 00:18:21,980
그리고 체인은 확실히
의 방법

375
00:18:21,980 --> 00:18:27,390
당신이 경우에 가장 효과적 일 것
당신은 해시 테이블에 데이터를 저장한다.

376
00:18:27,390 --> 00:18:30,890
그러나이 조합
배열과 연결리스트

377
00:18:30,890 --> 00:18:36,080
실제로 함께 해시 테이블을 형성
극적으로 당신의 능력을 향상

378
00:18:36,080 --> 00:18:40,550
대용량의 데이터를 저장하고
매우 신속하고 효율적으로 검색

379
00:18:40,550 --> 00:18:41,630
데이터를 통해.

380
00:18:41,630 --> 00:18:44,150
>> 하나는 여전히있다
거기에 데이터 구조

381
00:18:44,150 --> 00:18:48,700
그조차 조금있을 수 있습니다
보장의 측면에서 더 나은

382
00:18:48,700 --> 00:18:51,920
우리의 삽입, 삭제,
조회 시간도 빠릅니다.

383
00:18:51,920 --> 00:18:55,630
그리고 우리는 시도에 비디오가 표시됩니다.

384
00:18:55,630 --> 00:18:58,930
내가 더그 로이드 해요,이 CS50입니다.

385
00:18:58,930 --> 00:19:00,214