سوال: تفاوت hashtable & binary tree [بایگانی]

mehdi_turbo

چهارشنبه 14 مرداد 1388, 14:33 عصر

سلام دوست گرامي

در علم کامپیوتر،جدول درهم سازی یک داده ساختار است که از یک تابع هش استفاده می‌کند تا مقادیر معین یک نقشه را (یا به عبارتی همان کلیدها،مثلا نام افراد)به مقادیر خاصی(مثلا شماره تلفن آنها) نسبت دهد(مرتبط کند) .تابع هش برای این منظور استفاده می‌شود که مقادیر کلید را به اندیس های عناصر یک آرایه مر بوط کند(هش کند)،جایی که مقدار متناظر آن کلید جستجو می‌شود.
یک تابع هش ایده آل باید هر کلید ممکن را به یک خانه از آرایه متناظر کند،اما این امر در عمل به ندرت اتفاق می افتد.در بیشتر توابع هش فرض بر این است که به طور طبیعی تصادم رخ می‌دهد-یعنی دو کلید متفاوت مقدار هش یکسان پیدا می‌کنند و در نتیجه وارد یک خانه از آرایه می‌شوند-
در یک جدول با ابعاد خوب،متوسط هزینه (تعداد دستورالعمل ها)برای هر جستجو به تعداد عناصر نگهداری شده در آرایه بستگی ندارد. جداول هش بسیاری طراحی شده که امکان حذف و اضافهٔ اختیاری یک جفت کلیدومقدار هش اش را در یک هزینهٔ متوسط ثابت در هر عمل به ما می‌دهد.
در بسیاری از اوقات،جداول هش بسیار کارامد تر از درخت های جستجو یا هر داده ساختار جستجوی دیگری عمل می‌کند.به همین دلیل،جداول هش به طور گسترده درنرم افزارها،به خصوص در آرایه‌های شرکت پذیر،مرتب کردن پایگاه داده ،حافظه‌های نهان و مجموعه‌ها کاربرد دارند.
جداول هش نباید با هش لیست ها و درخت های هش که در پنهان شناسی cryptography وانتقال داده استفاده می‌شود اشتباه گرفته شود.

براي اطلاعات بيشتر به ادرس زير رجوع كنيد

ويكيپديا (http://fa.wikipedia.org/wiki/%D8%AC%D8%AF%D9%88%D9%84_%D8%AF%D8%B1%D9%87%D9%85% E2%80%8C%D8%B3%D8%A7%D8%B2%DB%8C)