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
โหนด struct * ต่อไป

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
คุณกลับจริงถ้ามันประสบความสำเร็จ
โหลดและเท็จอย่างอื่น

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
เพื่อให้แน่ใจว่ามันจะประสบความสำเร็จดังนั้นหาก
มันกลับโมฆะแล้วเราไม่ได้

30
00:01:34,700 --> 00:01:37,440
ประสบความสำเร็จในการเปิดพจนานุกรม
และเราต้องกลับเท็จ

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
พจนานุกรมและกลับเท็จ

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
ออกจากวงในขณะนี้

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
สิ่งเดียวที่คุณจำเป็นต้องรู้คือ
ที่นี้จะใช้เวลา char * คำ const,

55
00:03:04,010 --> 00:03:08,960
จึงสละสตริงเป็น input และ
กลับ 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
ขอให้สังเกตว่าเรากำลัง modding โดย 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
ตอนนี้กัญชา hashtable ที่เป็นปัจจุบัน
รายการที่เชื่อมโยงในตารางแฮชและ

65
00:03:38,830 --> 00:03:41,410
มันเป็นไปได้มากที่เป็นโมฆะเพียง

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
จุดที่จำไว้ว่าเราจำเป็นที่จะต้อง
รายการฟรีดังนั้นที่นี่เรา malloced

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
หากมีข้อผิดพลาดแล้วเราต้องการที่จะ
กลับเท็จเพราะการโหลดไม่ได้

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
ไฟล์และในที่สุดก็กลับจริงตั้งแต่
เราได้ประสบความสำเร็จในการโหลด

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
ผ่านใน char * คำว่า
สตริงผ่านไปในอยู่ในพจนานุกรมของเรา

93
00:05:07,530 --> 00:05:10,530
ดังนั้นถ้ามันอยู่ในพจนานุกรมถ้าเป็น
ในตารางแฮชของเราเราจะกลับมา

94
00:05:10,530 --> 00:05:13,380
จริงและถ้ามันไม่ได้
เราจะกลับเท็จ

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
เรากำลังจะดำเนินการต่อไปในขณะที่รายการไม่
ไม่เท่ากับโมฆะและจำไว้ว่า

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
กลับจริง

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
เรากลับเท็จเพื่อแสดงว่าเรา
ตารางแฮชไม่ได้มีคำนี้

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
ดังนั้นจึงเป็นไปไม่ได้สำหรับ unloads ที่เคย
กลับเท็จและเมื่อเรากำลังทำเรา

152
00:08:24,050 --> 00:08:25,320
เพียงแค่กลับจริง

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