ഹാഷ് ടേബിൾ
| ഹാഷ് ടേബിൾ | |||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Type | Unordered associative array | ||||||||||||||||||||
| Invented | 1953 | ||||||||||||||||||||
| Time complexity in big O notation | |||||||||||||||||||||
| |||||||||||||||||||||
ഹാഷ് ടേബിൽ എന്ന് പറയുന്നത് ഒരു തരത്തിലുള്ള വിവരശേഖരമാണ്(ഡാറ്റാ സ്ട്രക്‌ച്ചർ). ഡാറ്റ/വിവരത്തിനു മേലാണു ഒരു പ്രോഗ്രാമിൽ തിരുത്തലുകളും മറ്റ് ഓപ്പറേഷനുകളും കംപ്യൂട്ടറിൽ നടത്തുന്നത്. അത്തരം ഓപ്പറേഷൻസ് നടക്കുന്നതിനു, വിവരങ്ങൾ താത്കാലികമായി സൂക്ഷിയ്ക്കേണ്ടതുണ്ട്. ഈ വിവരം സൂക്ഷിയ്ക്കുന്നത് ഒരു പ്രത്യേക ഘടനയിലാകുന്നത്, ആ വിവരശേഖരത്തിന്മേലുള്ള (ഡാറ്റാസ്ട്രക്ച്ർ) ഓപ്പറേഷനെ കൂടുതൽ കാര്യക്ഷമമാക്കിയേക്കാം. മേൽ ചൊന്നതു പോലെ ഹാഷ്ടേബിൾ അത്തരമൊരു വിവരശേഖരമാണിത്.[2]
ലഘൂകരിച്ച് പറയുകയാണങ്കിൽ ഒരു ഹാഷ്ടേബിളിൽ കീയ് വാല്യു പെയറുകൾ ഉണ്ടാകും. ഓരോ വിവരത്തിനും/ഡാറ്റയ്ക്കും ഓരോ താക്കോൽ/കീയ് ഉണ്ടാകും. ഈ കീയ്/താക്കോൽ ഉപയോഗിച്ച് എളുപ്പം വാല്യൂ/വിവരത്തിനെ തിരഞ്ഞെടുക്കാനാകും. യഥാർത്ഥത്തിൽ കീയിൽ നിന്നും ഹാഷ് ഫൺക്ഷൻ ഉപയോഗിച്ച് ഒരു കൂട്ടം വിവരങ്ങൾ സൂക്ഷിച്ച ഇടത്തിലേക്കുള്ള ഒരു ഇൻഡെക്സ്/സൂചിക കണക്കാക്കുകയും. അവിടെ നിന്നും വിവരത്തിലേയ്ക്ക് കണക്ക് കൂട്ടി എത്തി ചേരുകയും ചെയ്യുകയാണു.
ഒരു മാതൃകാപരമായ ഹാഷ് ഫൺക്ഷൻ ഓരോ ഹാഷ് കീയും തികച്ചും വ്യത്യസ്തമായ വിവരങ്ങളിലേയ്ക്കുള്ള ചൂണ്ട് പലക നൽകേണ്ടതാണു. പക്ഷെ അത്തരമൊരു അവസ്ഥയിൽ എത്തി ചേരുക ബുദ്ധിമുട്ടാണു. മിക്കവാറും ഹാഷ്ഫൺകഷനുകൾ ഒന്നിലധികം കീയ്കളെ ഒരേ വിവര ശേഖരത്തിലേയ്ക്ക് എത്തിക്കാറുണ്ട്. ഇത്ത്രം അവസ്ഥയെ ഹാഷ് കൊളീഷൻ എന്നു വിളിയ്ക്കുന്നു. ഹാഷ് കൊളീഷൻ എന്ന ന്യൂനതയെ പരിഹരിക്കാനുള്ള പദ്ധതിയും ഒരു ഹാഷ്ടേബിൾ ഡാറ്റാസ്രക്ചർ ഡിസൈനിൽ ഉൾപ്പെടുത്തേണ്ടതുണ്ട്.
നല്ല അളവിലുള്ള ഹാഷ് പട്ടികയിൽ, ഓരോ ലുക്കപ്പിനുമുള്ള ശരാശരി സമയ സങ്കീർണ്ണത പട്ടികയിൽ സംഭരിച്ചിരിക്കുന്ന ഘടകങ്ങളുടെ എണ്ണത്തിൽ നിന്ന് സ്വതന്ത്രമാണ്. പല ഹാഷ് ടേബിൾ ഡിസൈനുകളും ആർബിട്ടറി ഇൻസെർഷനും, കീ-പേയർ ജോഡികൾ ഇല്ലാതാക്കാനും അനുവദിക്കുന്നു, മോർട്ടിസന്റ് കോൺസ്റ്ററ്റിൽ ഓരോ ഓപ്പറേഷനിലും ആവറേജ് കോസ്റ്റ് വരുന്നു.[3][4][5]
അവലംബം
[തിരുത്തുക]- ↑ Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2009). Introduction to Algorithms (3rd ed.). Massachusetts Institute of Technology. pp. 253–280. ISBN 978-0-262-03384-8.
- ↑ Mehlhorn, Kurt; Sanders, Peter (2008), "4 Hash Tables and Associative Arrays", Algorithms and Data Structures: The Basic Toolbox (PDF), Springer, pp. 81–98
- ↑ Leiserson, Charles E. (Fall 2005). "Lecture 13: Amortized Algorithms, Table Doubling, Potential Method". course MIT 6.046J/18.410J Introduction to Algorithms. Archived from the original on August 7, 2009.
- ↑ Knuth, Donald (1998). The Art of Computer Programming. Vol. 3: Sorting and Searching (2nd ed.). Addison-Wesley. pp. 513–558. ISBN 978-0-201-89685-5.
- ↑ Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001). "Chapter 11: Hash Tables". Introduction to Algorithms (2nd ed.). MIT Press and McGraw-Hill. pp. 221–252. ISBN 978-0-262-53196-2.