ഹാഷ് ടേബിൾ
Hash table | |||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Type | Unordered associative array | ||||||||||||||||||||
Invented | 1953 | ||||||||||||||||||||
Time complexity in big O notation | |||||||||||||||||||||
|
ഹാഷ് ടേബിൽ എന്ന് പറയുന്നത് ഒരു തരത്തിലുള്ള വിവരശേഘരമാണു(ഡാറ്റാ സ്ട്രക്ച്ചർ). ഡാറ്റ/വിവരത്തിനു മേലാണു ഒരു പ്രോഗ്രാമിൽ തിരുത്തലുകളും മറ്റ് ഓപ്പറേഷനുകളും കംബ്യൂട്ടറിൽ നടത്തുന്നത്. അത്തരം ഓപ്പറേഷൻസ് നടക്കുന്നതിനു, വിവരങ്ങൾ താത്കാലികമായി സൂക്ഷിയ്ക്കേണ്ടതുണ്ട്. ഈ വിവരം സൂക്ഷിയ്ക്കുന്നത് ഒരു പ്രത്യേക ഘടനയിലാകുന്നത്, ആ വിവരശേഘരത്തിന്മേലുള്ള (ഡാറ്റാസ്ട്രക്ച്ർ) ഓപ്പറേഷനെ കൂടുതൽ കാര്യക്ഷമമാക്കിയേക്കാം. മേൽ ചൊന്നതു പോലെ ഹാഷ്ടേബിൾ അത്തരമൊരു വിവരശേഘരമാണു.
ലഘൂകരിച്ച് പറയുകയാണേൽ ഒരു ഹാഷ്ടേബിളിൽ കീയ് വാല്യു പെയറുകൾ ഉണ്ടാകും. ഓരോ വിവരത്തിനും/ഡാറ്റയ്ക്കും ഓരോ താക്കോൽ/കീയ് ഉണ്ടാകും. ഈ കീയ്/താക്കോൽ ഉപയോഗിച്ച് എളുപ്പം വാല്യൂ/വിവരത്തിനെ തിരഞ്ഞെടുക്കാനാകും. യഥാർത്ഥത്തിൽ കീയിൽ നിന്നും ഹാഷ് ഫൺക്ഷൻ ഉപയോഗിച്ച് ഒരു കൂട്ടം വിവരങ്ങൾ സൂക്ഷിച്ച ഇടത്തിലേക്കുള്ള ഒരു ഇൻഡെക്സ്/സൂചിക കണക്കാക്കുകയും. അവിടെ നിന്നും വിവരത്തിലേയ്ക്ക് കണക്ക് കൂട്ടി എത്തി ചേരുകയും ചെയ്യുകയാണു.
ഒരു മാതൃകാപരമായ ഹാഷ് ഫൺക്ഷൻ ഓരോ ഹാഷ് കീയും തികച്ചും വ്യത്യസ്തമായ വിവരങ്ങളിലേയ്ക്കുള്ള ചൂണ്ട് പലക നൽകേണ്ടതാണു. പക്ഷെ അത്തരമൊരു അവസ്ഥയിൽ എത്തി ചേരുക ബുദ്ധിമുട്ടാണു. മിക്കവാറും ഹാഷ്ഫൺകഷനുകൾ ഒന്നിലധികം കീയ്കളെ ഒരേ വിവര ശേഘരത്തിലേയ്ക്ക് എത്തിക്കാറുണ്ട്. ഇത്ത്രം അവസ്ഥയെ ഹാഷ് കൊളീഷൻ എന്നു വിളിയ്ക്കുന്നു. ഹാഷ് കൊളീഷൻ എന്ന ന്യൂനതയെ പരിഹരിക്കാനുള്ള പദ്ധതിയും ഒരു ഹാഷ്ടേബിൾ ഡാറ്റാസ്രക്ചർ ഡിസൈനിൽ ഉൾപ്പെടുത്തേണ്ടതുണ്ട്.
- ↑ Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2009). Introduction to Algorithms (3rd പതിപ്പ്.). Massachusetts Institute of Technology. പുറങ്ങൾ. 253–280. ISBN 978-0-262-03384-8.