جدول درهمکسازی
From Wikipedia, the free encyclopedia
جدول درهمکسازی یا جدول چکیدهسازی[1] یا جدول هش (به انگلیسی: hash table)، در علوم رایانه، نوعی ساختمان داده است که مقدارهایی[2] که باید ذخیره شوند را به وسیله تابع هش (درهم سازی) با کلیدهای ویژهای مرتبط میسازد. عملیات اولیهای که این جدول تسهیل میکند عمل مراجعه است. به این معنی که کاربر میتواند با سرعتی کارآمد داده مورد نظرش را در آن بیابد. در جدولهای هش همچنین افزودن دادههای جدید در زمان کم امکانپذیر است. زمان لازم برای جستجو و افزودن وابسته به نوع جدول و میزان دادهها هستند. این زمان میتواند با انتخاب جدول مناسب به مرتبه زمانی O(1) برسد.
جدول درهم سازی | |||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
گونه | آرایهی انجمنیِ بیترتیب | ||||||||||||||||||||
سال اختراع | ۱۹۵۳ میلادی | ||||||||||||||||||||
زمان اجرای الگوریتم بر پایه نماد O بزرگ | |||||||||||||||||||||
|
یک تابع هش ایدئال باید هر کلید ممکن را به یک خانه از آرایه متناظر کند، اما این امر در عمل به ندرت اتفاق میافتد. در بیشتر توابع هش فرض بر این است که بهطور طبیعی تصادم رخ میدهد، یعنی دو کلید متفاوت، مقدار هش یکسان پیدا میکنند و در نتیجه وارد یک خانه از آرایه میشوند.
در یک جدول با ابعاد خوب، متوسط هزینه (تعداد دستورالعملها) برای هر جستجو به تعداد عناصر نگهداری شده در آرایه بستگی ندارد. جداول هش بسیاری طراحی شده که مرتبه زمانی حذف و افزودن یک جفت کلید و مقدار اختیاری بهطور متوسط ثابت است.
در بسیاری از اوقات، جداول درهمسازی بسیار کارآمدتر از درختهای جستجو یا هر دادهساختار جستجوی دیگری عمل میکند. به همین دلیل، جداول هش بهطور گسترده درنرمافزارها، به خصوص در آرایههای شرکتپذیر، ساختار فهرست پایگاهداده، حافظههای نهان و مجموعهها کاربرد دارند.
جداول هش نباید با هش لیستها و درختهای هش که در رمزنگاری و انتقال داده استفاده میشود اشتباه گرفته شوند.