हैश टेबल कैसे काम करता है? यह तेजी से है "से * का चयन करें .."

Question

मान लें, मेरे पास है:

 
Key | Indexes | Key-values 
----+---------+------------ 
001 | 100001 | Alex 
002 | 100002 | Micheal 
003 | 100003 | Daniel 

कहते हैं, हम 001, खोज कितनी तेजी से खोज प्रक्रिया हैश तालिका का उपयोग करने के लिए करना चाहते हैं की सुविधा देता है?

क्या यह वही नहीं है जैसा हम mysql में "SELECT * से .." का उपयोग करते हैं? मैंने बहुत कुछ पढ़ा, वे कहते हैं, "चयन *" शुरुआत से अंत तक खोज रहा है, लेकिन हैश टेबल नहीं है? क्यों और कैसे?

हैश तालिका का उपयोग करके, क्या हम उन रिकॉर्ड्स को कम कर रहे हैं जिन्हें हम खोज रहे हैं? कैसे?

क्या कोई यह दिखा सकता है कि mysql क्वेरी कोड में हैश तालिका प्रक्रिया को कैसे सम्मिलित करना और पुनर्प्राप्त करना है? उदाहरण के लिए,

SELECT * from table1 where hash_value="bla" ... 

अन्य परिदृश्य: अनुक्रमित S0001, S0002, T0001, T0002, आदि MySQL में की तरह हैं तो मैं इस्तेमाल कर सकते हैं:

SELECT * from table WHERE value = S* 

यह एक ही नहीं है और तेजी से?

Answer 1

एक साधारण हैश तालिका आइटम को कई सूचियों पर रखकर काम करती है, केवल एक के बजाय। यह प्रत्येक आइटम को रखने के लिए कौन सी सूची चुनने के लिए एक बहुत तेज़ और दोहराने योग्य (यानी गैर-यादृच्छिक) विधि का उपयोग करता है। तो जब आइटम को फिर से ढूंढने का समय हो, तो यह पता लगाने के लिए कि कौन सी सूची देखना है, और फिर उस सूची में एक सामान्य (धीमी) रैखिक खोज करता है।

वस्तुओं को 17 सूचियों में विभाजित करके, खोज 17 गुना तेज हो जाती है, जो एक अच्छा सुधार है।

हालांकि निश्चित रूप से यह केवल तभी सही है जब सूचियां लगभग समान लंबाई हों, इसलिए सूचियों के बीच वस्तुओं को वितरित करने की एक अच्छी विधि चुनना महत्वपूर्ण है।

अपनी उदाहरण तालिका में, पहला कॉलम कुंजी है, जिस चीज़ को हमें आइटम ढूंढने की आवश्यकता है। और मान लीजिए कि हम 17 सूचियां बनाए रखेंगे।कुछ डालने के लिए, हम हैशिंग नामक कुंजी पर एक ऑपरेशन करते हैं। यह सिर्फ कुंजी को एक संख्या में बदल देता है। यह एक यादृच्छिक संख्या नहीं लौटाता है, क्योंकि इसे हमेशा एक ही कुंजी के लिए एक ही संख्या को वापस करना होगा। लेकिन साथ ही, संख्याओं को व्यापक रूप से "फैलाना" होना चाहिए।

फिर हम जिसके परिणामस्वरूप संख्या और उपयोग मापांक ले हमारे सूची के आकार के लिए नीचे हटना:

Hash(key) % 17 

यह सब बहुत तेज होता है। बाद में

_lists[Hash(key % 17)].Add(record); 

और फिर, का उपयोग कर कुंजी है कि आइटम खोजने के लिए:: हमारे सूचियों एक सरणी में हैं, इसलिए

Record found = _lists[Hash(key % 17)].Find(key); 

ध्यान दें कि प्रत्येक सूची बस किसी भी कंटेनर प्रकार, या एक लिंक्ड सूची हो सकता है कक्षा जिसे आप हाथ से लिखते हैं। जब हम उस सूची में Find निष्पादित करते हैं, तो यह धीमा तरीका काम करता है (प्रत्येक रिकॉर्ड की कुंजी की जांच करें)।

Answer 2

हैश टेबल ओ (1) लागत पर प्रविष्टियों का पता लगाने के लिए बहुत अच्छे हैं जहां कुंजी (जिसका उपयोग हैशिंग के लिए किया जाता है) पहले ही ज्ञात है। वे संग्रह पुस्तकालयों और डेटाबेस इंजन दोनों में व्यापक रूप से उपयोग में हैं। आपको इंटरनेट पर उनके बारे में बहुत सारी जानकारी मिलनी चाहिए। आप Wikipedia से क्यों शुरू नहीं करते हैं या बस Google खोज करते हैं?

मुझे mysql का विवरण नहीं पता है। यदि वहां "हैश टेबल" नामक एक संरचना है, तो शायद यह एक प्रकार की तालिका होगी जो कुंजी को ढूंढने के लिए हैशिंग का उपयोग करती है। मुझे यकीन है कि कोई और आपको इसके बारे में बताएगा। =)

संपादित करें: (जवाब में टिप्पणी करने के लिए)

ठीक है। मैं एक पूरी तरह से सरलीकृत स्पष्टीकरण बनाने की कोशिश करूंगा: एक हैश तालिका एक सारणी है जहां प्रविष्टियां कुंजी के फ़ंक्शन के आधार पर स्थित होती हैं। उदाहरण के लिए, कहें कि आप व्यक्तियों के एक समूह के बारे में जानकारी स्टोर करना चाहते हैं। यदि आप इसे एक सादे बिना छेड़छाड़ वाले सरणी में संग्रहीत करते हैं, तो आपको जिस प्रविष्टि को ढूंढ रहे हैं उसे ढूंढने के लिए आपको अनुक्रमों में तत्वों को फिर से सक्रिय करना होगा। औसतन, इसे एन/2 तुलना की आवश्यकता होगी।

यदि, इसके बजाय, आप व्यक्तियों के पहले चरित्र के आधार पर इंडेक्स पर सभी प्रविष्टियां डालते हैं। (ए = 0, बी = 1, सी = 2 इत्यादि), जब तक आप पहले नाम को जानते हैं तब तक आप तुरंत सही प्रविष्टि पा सकेंगे। यह मूल विचार है। आपको शायद एहसास होगा कि एक ही पहले अक्षर वाले कई प्रविष्टियों का समर्थन करने के लिए कुछ विशेष हैंडलिंग (प्रविष्टियों की सूचियों को पुनर्स्थापित करना या अनुमति देना) आवश्यक है। यदि आपके पास एक अच्छी तरह से आयामी हैश तालिका है, तो आप जिस आइटम को खोज रहे हैं उसे सीधे प्राप्त करने में सक्षम होना चाहिए। इसका मतलब है कि विशेष हैंडलिंग के अस्वीकरण के साथ मैंने लगभग एक तुलना की है।

Answer 3

मुझे लगता है कि आप उस आईडी को प्राप्त करने के लिए हैश फ़ंक्शन का उपयोग कर सकते हैं, जिसे आप चुनना चाहते हैं।

चुनें * मेज कहां मूल्य = hash_fn (whatever_input_you_build_your_hash_value_from)

तो फिर तुम पंक्ति आप चयन करना चाहते का आईडी पता करने के लिए और एक सटीक क्वेरी कर सकते हैं की जरूरत नहीं है से की तरह। चूंकि आप जानते हैं कि आपके पास हैश मान फ़ॉर्म बनाने वाले इनपुट की पंक्ति हमेशा एक ही आईडी होगी और आप हमेशा इस आईडी को हैश फ़ंक्शन के माध्यम से पुन: बना सकते हैं।

हालांकि यह तालिका के आकार और अधिकतम हैशव्यू के आधार पर हमेशा सत्य नहीं होता है (आपके पास अक्सर आपके हैश में "एक्स मॉड हैश-टेबल-साइज" होता है)। इसका ख्याल रखने के लिए आपके पास एक निर्धारित आईडी रणनीति होनी चाहिए जब आप एक ही आईडी के साथ दो मान प्राप्त करते हैं। इस रणनीति पर अधिक जानकारी के लिए आपको Wikipedia जांचना चाहिए, इसे टकराव हैंडलिंग कहा जाता है और उसी लेख में हैश-टेबल के रूप में उल्लेख किया जाना चाहिए।

MySQL शायद ओ (1) सुविधा norheim.se (ऊपर) के कारण कहीं भी हैशटेबल्स का उपयोग करता है।

Answer 4

इस बारे में चिंता न करें कि MySQL आंतरिक रूप से रिकॉर्ड्स का पता लगाने के लिए क्या कर रहा है। डेटाबेस का काम आपके लिए उस तरह की चीज करना है। बस एक SELECT [columns] FROM table WHERE [condition]; क्वेरी चलाएं और डेटाबेस को आपके लिए एक क्वेरी योजना उत्पन्न करने दें। ध्यान दें कि आप SELECT * का उपयोग नहीं करना चाहते हैं, क्योंकि यदि आपने कभी भी तालिका में एक कॉलम जोड़ दिया है जो आपके सभी पुराने प्रश्नों को तोड़ देगा जो किसी निश्चित क्रम में कॉलम की एक निश्चित संख्या पर निर्भर करते हैं।

तुम सच में पता है कि (यह पता करने के लिए अच्छा है, लेकिन यह अपने आप को लागू नहीं है!: कि एक डेटाबेस का उद्देश्य है) हुड के नीचे हो रहा है चाहते हैं, तो आप को पता है कि अनुक्रमित रहे हैं की जरूरत है और कैसे वे काम करते हैं। यदि किसी तालिका में WHERE क्लॉज में शामिल कॉलम पर कोई अनुक्रमणिका नहीं है, तो, जैसा कि आप कहते हैं, डेटाबेस को आपकी स्थिति से मेल खाने वाले लोगों को ढूंढने के लिए तालिका में प्रत्येक पंक्ति के माध्यम से खोजना होगा। लेकिन अगर एक सूचकांक है, तो डेटाबेस आपके द्वारा इच्छित पंक्तियों के सटीक स्थान को खोजने के लिए सूचकांक की खोज करेगा, और सीधे उन्हें सीधे कूद देगा। इंडेक्स आमतौर पर B+-trees के रूप में लागू होते हैं, एक प्रकार का खोज पेड़ जो विशिष्ट तत्व का पता लगाने के लिए बहुत कम तुलना करता है। एक विशिष्ट कुंजी के लिए बी-पेड़ खोजना बहुत तेज़ है। MySQL हैश इंडेक्स का उपयोग करने में भी सक्षम है, लेकिन ये डेटाबेस उपयोगों के लिए धीमे होते हैं। हैश इंडेक्स आमतौर पर लंबी चाबियों (विशेष रूप से चरित्र तार) पर अच्छा प्रदर्शन करते हैं, क्योंकि वे एक निश्चित हैश आकार में कुंजी के आकार को कम करते हैं। डेटा प्रकारों जैसे कि पूर्णांक और वास्तविक संख्याओं के लिए, जिनमें एक अच्छी तरह से परिभाषित आदेश और निश्चित लंबाई है, बी-पेड़ की आसान खोज क्षमता आमतौर पर बेहतर प्रदर्शन प्रदान करती है।

आप इंडेक्सिंग पर MySQL manual और PostgreSQL manual में अध्यायों को देखना चाहेंगे।

Answer 5

http://en.wikipedia.org/wiki/Hash_table

हैश तालिकाओं में स्मृति डेटा संरचनाओं के रूप में इस्तेमाल किया जा सकता है। लगातार डेटा संरचनाओं के उपयोग के लिए हैश टेबल भी अपनाया जा सकता है; database indices कभी-कभी हैश टेबल के आधार पर डिस्क-आधारित डेटा संरचनाओं का उपयोग करते हैं, हालांकि balanced trees अधिक लोकप्रिय हैं।