هشنگ چیست؟کار ، انواع و برنامه ها

Hashing یک مقدار عددی را با استفاده از توابع هش و الگوریتم ها به یک رشته اختصاص می دهد تا بازیابی داده ها سریعتر شود و رمزگذاری آن را فعال کند.

نویسنده فنی Chiradeep Basumallick 6 ژوئن 2023

• هشویی به عنوان فرایند اختصاص یک مقدار عددی به یک رشته الفبایی با تبدیل ابتدا آن به یک مقدار عددی دیگر و ذخیره آن در یک جدول فهرست بندی شده تعریف می شود تا بازیابی داده ها سریعتر و/یا ماسک کردن داده ها برای رمزگذاری ، انجام شده توسط یک عملکرد هش.
• در این مقاله توضیح می دهد که چگونه هشویی ، انواع آن و عملکردهای مهم آن کار می کند.

فهرست مطالب

• هشنگ چیست؟
• هشنگ چگونه کار می کند؟
• انواع هش
• توابع هشویی

هشنگ چیست؟

هشویی فرآیند اختصاص یک مقدار عددی به یک رشته الفبایی با تبدیل ابتدا آن به یک مقدار عددی دیگر و ذخیره آن در یک جدول فهرست بندی شده است تا بازیابی داده ها را سریعتر و/یا نقاب زدن داده ها برای رمزگذاری ، انجام شده توسط یک عملکرد هش انجام دهد.

چگونه هشویی رشته ها را به مقادیر عددی تبدیل می کند

هشدار برای تبدیل یک کلید یا رشته کاراکتر به مقدار دیگری استفاده می شود. این اغلب با یک مقدار یا متغیر با طول ثابت کوچکتر منعکس می شود که رشته اصلی را منعکس می کند و مکان یابی یا استفاده را ساده تر می کند.

متداول ترین استفاده از هشویی ، ایجاد جداول هش است. یک جدول هش در مجموعه ای که می توان از طریق شاخص آن به آن دسترسی پیدا کرد ، جفت های ارزش کلیدی را در خود جای داده است. با توجه به اینکه جفت های ارزش کلیدی بی نهایت هستند ، عملکرد هش ممکن است مقادیر را با اندازه جدول مطابقت دهد. مقدار هش سپس به عنوان نشانگر برای یک عنصر خاص استفاده می شود.

یک تابع هش مقادیر جدیدی را بر اساس یک تکنیک هشویی ریاضی ایجاد می کند ، که اغلب به آن یک مقدار هش یا هش گفته می شود. یک هش خوب همیشه از تکنیک هشویی یک طرفه برای جلوگیری از تبدیل هش به کلید اصلی استفاده می کند.

هشویی برای جستجوی و بازیابی داده ها ، امضاهای دیجیتال ، امنیت سایبری و رمزنگاری از جمله بسیاری از برنامه های دیگر قابل استفاده است.

چرا هشنگ ضروری است؟

هر روز ، میزان داده های موجود در اینترنت به صورت تصاعدی افزایش می یابد و حفظ این داده ها به طور مؤثر همیشه یک چالش است. این مقدار از داده ها ممکن است برای برنامه نویسی روتین خیلی زیاد نباشد. با این حال ، هنوز هم باید به راحتی و کارآمد ذخیره ، بازیابی و پردازش شود. مدل داده آرایه یک ساختار داده نسبتاً متداول برای این منظور است.

مجموعه ای از چیزهایی که در مناطق حافظه متناوب ذخیره شده اند ، آرایه ای را تشکیل می دهند. هدف این است که چندین مدخل را که در یک گروه قرار می گیرند ، گروه بندی کنیم.

بنابراین این سؤال مطرح می شود که چرا در صورت وجود مدل های داده آرایه ، ساختار داده جدید ضروری است! این سؤال با اصطلاح "کارآیی" پاسخ داده می شود. اگرچه ذخیره در یک آرایه به زمان (1) زمان نیاز دارد ، جستجوی داخل آن حداقل به زمان O (ورود به سیستم) نیاز دارد.

O (1) زمان ثابت را نشان می دهد ، که نشان می دهد الگوریتم های زمان ثابت همیشه برای همان زمان اجرا می شوند. پیچیدگی زمان ثابت الگوریتمی را توصیف می کند که زمان اجرای آن مستقل از تعداد ورودی ها است. در مقابل ، زمان O (log n) نشان می دهد که با افزایش طول ورودی ، مقدار کل عملیات به آرامی افزایش می یابد. این بدان معنی است که زمان به صورت خطی افزایش می یابد در حالی که ‘n 'به صورت نمایی رشد می کند.

به نظر می رسد O (log n) زمان کمی است. با این حال ، با جمع آوری داده های بزرگ ، ممکن است مشکلات بسیاری ایجاد کند و مدل داده های آرایه را ناکارآمد می کند.

جستجوی یک مدل داده ای که می تواند داده ها را حفظ کرده و در زمان ثابت یا زمان (1) زمان جستجو را انجام دهد ، لازم بود. به همین دلیل ساختار داده هشدار معرفی شد. با توسعه مدل داده هش ، اکنون امکان نگه داشتن و بازیابی اطلاعات به طور مداوم با سهولت نسبی امکان پذیر است.

ساختار داده هش چیست؟

معماری هش یک مدل داده جدولی برای ذخیره همکاران داده است. داده ها در قالب آرایه در جدول نگهداری می شوند. با این حال ، بر خلاف یک آرایه معمولی ، به هر عنصر داده یک شماره شاخص منحصر به فرد اختصاص داده می شود. هنگامی که شاخص داده های مورد نیاز را در اختیار داشتیم ، دسترسی به اطلاعات بسیار سریع می شود.

به این ترتیب ، آن را به یک مدل داده تبدیل می شود که در آن اقدامات علاوه بر این و بازیابی بدون در نظر گرفتن اندازه داده ها سریع هستند. از آرایه ای مانند یک مرکز ذخیره سازی استفاده می کند و از یک الگوریتم هشدار برای ساخت یک شاخص برای درج یا یافتن یک عنصر استفاده می کند.

به عنوان مثال ، اگر مقدار کلیدی جین باشد و محتوا شماره تلفن باشد ، ما هنگام ارائه مقدار کلیدی به عملکرد هش ، آن را به شرح زیر منتقل می کنیم:

هنگامی که کلید را از طریق عملکرد هش پردازش می کنیم ، شاخص را تولید می کند.

مثال بالا کلید ، جین را در فهرست 2461 اضافه می کند.

کل فرآیند هشویی با استفاده از سه مؤلفه کار می کند:

• کلید: یک کلید می تواند هر متن یا شماره ای باشد که به عنوان ورودی به عملکرد هش ارائه می شود ، که شاخص یا موقعیت ذخیره سازی یک مورد را در یک ساختار داده تعیین می کند. در این سناریو ، جین کلید است.
• عملکرد هش: عملکرد هش یک کلید را به عنوان ورودی می پذیرد و شاخص یک جزء را در یک آرایه معروف به جدول هش تولید می کند. این شاخص به عنوان شاخص هش گفته می شود.
• جدول هش: جدول هش به مدل داده ای اشاره دارد که کلیدها را از طریق یک تابع درهم به مقادیر پیوند می دهد. Hash داده ها را به صورت تداعی در یک آرایه با یک شاخص منحصر به فرد برای هر مقدار داده نگهداری می کند.

هش برای چه مواردی استفاده می شود؟

هش کردن چندین کاربرد کلیدی دارد، مانند:

1. هش در امنیت سایبری

هش توسط چندین تکنیک رمزگذاری برای بهبود امنیت سایبری استفاده می شود. بدون کلید رمزگشایی، هکرها نمی توانند پیام ها و ورودی های هش شده را تفسیر کنند. به عنوان مثال، اگر هکرها به یک پایگاه داده دسترسی پیدا کنند و اطلاعاتی مانند "جین دو، شماره تلفن 2461" را کشف کنند، ممکن است فورا از آن برای اهداف مخرب استفاده کنند. یک مقدار هش شده مانند "b4gh8" برای عوامل تهدید بدون کلید رمزگشایی بی معنی است. از این رو، هش از رمزهای عبور ذخیره شده در پایگاه داده محافظت می کند.

2. هش برای عملیات داده سریعتر

هش کردن نگاشت داده های شی به یک مقدار نمایش با استفاده از توابع یا الگوریتم ها است. هنگام جستجوی این اشیا در نقشه داده شی، می توان از هش برای محدود کردن جستجوها استفاده کرد. این به طور قابل توجهی فرآیندهای داده را تسریع می کند. به عنوان مثال، با جداول هش، برنامه نویسان داده ها را به صورت جفت کلید-مقدار، مانند رکورد مشتری، ذخیره می کنند. کلید داده ها و عملکردها را مانند یک ورودی شناسایی می کند، در حالی که کد هش یا عدد صحیح برای تولید خروجی نقشه برداری می شود.

3. هش در رمزنگاری

برای حفاظت از داده ها، علم رمزنگاری از الگوریتم های هش متعددی استفاده می کند. به عنوان مثال، الگوریتم هش ایمن (SHA)، یک تکنیک معمولی است که برای تولید خلاصه های پیام 160 بیتی (یک کپی عددی با اندازه ثابت از ماده یک پیام) استفاده می شود. SHA-2 برای ایجاد خلاصه پیام بزرگتر (224 بیت) استفاده می شود. SHA-3 جانشین SHA-2 است و همه این الگوریتم ها بر اساس هش ساخته شده اند.

4. هش در امضای دیجیتال

یکی از اجزای اساسی سیستم های امضای دیجیتال هش کردن است. توابع هش را می توان همراه با رمزگذاری برای ارائه یک مقدار هش ( خلاصه پیام) استفاده کرد که به عنوان اثر انگشت دیجیتالی متمایز عمل می کند. این نشان می دهد که هر گونه تغییر در داده های ورودی منجر به یک نتیجه کاملاً متفاوت (مقدار هش) می شود. در نتیجه، این به اعتبارسنجی گواهی های دیجیتال و منابع آنها کمک می کند.

5. هش در ارزهای دیجیتال

استخراج بیت کوین از یک عملکرد هش Double Sha-256 استفاده می کند. پس از اتمام معامله ، به گره blockchain خاص دو شماره انتخاب شده به طور تصادفی اختصاص داده می شود. Nonce ، یک عدد صحیح 32 بیتی ، ابتدا تعبیه شده است. این یک هش یا شماره 256 بیتی ایجاد می کند ، که حاوی اطلاعاتی در مورد نمونه ، از جمله زمان ، مکان و نویسنده است (توسط رله شده). قبل از افزودن بلوک به زنجیره ای ، معدنچیان باید اثبات کار ایجاد کنند. اینگونه است که بیت کوین کار می کند.

هشنگ چگونه کار می کند؟

برای درک چگونگی عملکردهای هشویی ، مثال زیر را ببینید. فرض کنید ما می خواهیم مجموعه ای از رشته ها "AB ،" "CD" و "EFG" را در یک جدول ذخیره کنیم.

در این حالت ، هدف از هذیان ، جستجوی سریع یا به روزرسانی داده های موجود در جدول در O (1) زمان است و ترتیب رشته های موجود در جدول بی ربط است. مجموعه مشخص شده رشته ها می تواند به عنوان یک کلید باشد و رشته به تنهایی به عنوان مقدار کلید عمل می کند. چگونه می توانیم مقدار تطبیق با کلید را ذخیره کنیم. در اینجا ، ما از یک فرمول ریاضی ساده استفاده خواهیم کرد: Mod.

MOD یک عمل محاسباتی است که باقیمانده را محاسبه می کند وقتی یک ورودی توسط دیگری تقسیم می شود. به عنوان مثال ، 14 Mod 6 = 2. در مثال ما ، ما به عنوان الگوریتم برای محاسبه جفت ارزش کلید استفاده خواهیم کرد. با این حال ، الگوریتم های دنیای واقعی از فرمول های بسیار پیچیده ای استفاده می کنند که رمزگشایی یا رمزگشایی آنها دشوار است.

• ما می دانیم که توابع هش (که یک فرمول ریاضی است) برای رسیدن به مقدار هش استفاده می شود. برای فرمول ما ، Mod را انتخاب کرده ایم.
• بنابراین بیایید "A" = 1 ، ‘B" = 2 و غیره را به همه شخصیت های الفبایی اختصاص دهیم.

مقدار عددی با جمع بندی همه شخصیت های رشته به شرح زیر محاسبه می شود:

• اکنون فرض کنید که ما یک جدول 6 سلولی برای نگه داشتن این رشته ها داریم. عملکرد هش مورد استفاده در این مورد ، کل ارقام موجود در (کلید) Mod 6 (اندازه جدول) است. با محاسبه کل عددی هر رشته در مجموعه ، تقسیم شده توسط 6 برای رسیدن به قسمت باقیمانده ، می توانیم موقعیت رشته را در آرایه تشخیص دهیم.
• سپس مکان جدول را که در آن هر مقدار رشته را ذخیره می کنیم محاسبه می کنیم:

"AB" 5 مود 6 = 6 است

"سی دی" 7 مود 6 = 1 است

"FH" 14 مود 6 = 2 است

حال ، اگر مجبور شوید FG را به جای FH ذخیره کنید ، چه می کنید؟هشویی به شرح زیر است:

بنابراین ، FG 13 Mod 6 = 1 است.

با این حال ، رشته CD در حال حاضر 1 در جدول هشویی اشغال کرده است. چنین سناریویی به عنوان برخورد شناخته می شود و ناشی از یک عملکرد الگوریتمی ضعیف است.

برخورد در کار هشویی چیست؟

برخورد یا برخورد هش در علوم کامپیوتر رخ می دهد که دو بیت داده در یک جدول هش دارای همان ارزش هش باشد. اگرچه الگوریتم های هش برای مقاوم در برابر برخورد طراحی شده اند ، اما بعضی اوقات می توانند داده های متمایز را به همان هش ترجمه کنند. دلیل این امر اصل کبوتر است.

اصل کبوتر ادعا می کند که اگر چیزهای "n" در ظروف ‘M قرار بگیرند و N بیش از M باشد ، حداقل یک ظرف باید بیش از یک مورد را در خود نگه دارد. این گاهی اوقات می تواند به نتایج غیر منتظره منجر شود. با فرض اینکه جمعیت شهر نیویورک بیش از حداکثر تعداد رشته های مو است که می تواند روی سر انسان وجود داشته باشد ، اصل کبوتر نشان می دهد که باید حداقل دو نفر در لندن با همان تعداد موهای مو وجود داشته باشند.

کاربران با قصد مخرب ممکن است از پدیده های برخورد هش برای تقلید ، دسترسی یا اصلاح داده ها استفاده کنند. برای مقابله با این و تضمین یکپارچگی نتایج رمزگذاری شده ، کارشناسان امنیت سایبری ممکن است شامل تعداد تصادفی در الگوریتم هش باشند. این تکنیک ، معروف به "نمک" ، حتی اگر داده ها مشابه باشد (مانند FG = 1 و CD = 1 در مثال ما) خروجی متمایز را تضمین می کند.

انواع هش

هش می تواند از چهار نوع زیر باشد:

1. هشویی بی اهمیت

اطلاعات به طور مستقیم به یک شاخص در داخل یک جدول هش در هشویی بی اهمیت ، که اغلب به آن نقشه برداری از فهرست گفته می شود ، ترجمه می شود. این رویکرد معمولاً از عملکرد هش هویت استفاده می کند ، که هرگونه داده ورودی را به سمت خود ترجمه می کند. در این مثال ، از کلید داده ها به عنوان شاخص در جدول هش استفاده می شود در حالی که مقدار مربوطه در آن موقعیت ذخیره می شود.

الگوریتم ساده لوحانه به سادگی کلید "B" را به فهرست ‘2" در جدول Hash ترجمه می کند و مقدار "اپل" را در آن موقعیت ذخیره می کند.

سادگی هشویی بی اهمیت از مزایای اصلی آن است. عملکرد هش برای درک و اجرای ساده است و بازیابی داده ها با استفاده از کلید ساده است. با این حال ، همچنین محدودیت های خاصی دارد. با توجه به این شرط که طول جدول هش برابر با تعداد کلیدها باشد ، استفاده از مجموعه داده های ریز محدود است. علاوه بر این ، برخوردها انجام نمی شود. این بدان معنی است که اگر دو کلید به یک شاخص یکسان ترجمه شوند ، یکی از مقادیر رونویسی می شود.

2. هشویی دوتایی

جداول هش از هشویی مضاعف به عنوان یک رویکرد وضوح برخورد استفاده می کنند. استفاده از دو عملکرد هش دو نتیجه هش مجزا برای یک کلید معین ایجاد می کند. عملکرد هش اول برای تعیین مقدار هش اولیه استفاده می شود ، در حالی که از دوم برای تعیین طول مرحله دنباله کاوش استفاده می شود (لیست چک مکان هایی که در صورت برخورد به عنوان گزینه های دیگر مورد بررسی قرار می گیرند).

از آنجا که از دو کارکرد هش برای محاسبه مقدار هش و اندازه پله استفاده می کند ، هش دوگانه پتانسیل را برای نرخ برخورد پایین فراهم می کند. این بدان معنی است که احتمال برخورد کمتر از سایر روشهای وضوح برخورد است.

با این حال ، هشدار مضاعف با برخی معایب همراه است. این امر به استفاده از دو الگوریتم هش نیاز دارد ، که ممکن است تلاش محاسباتی عملیات درج و جستجو را افزایش دهد. ثانیا ، برای به دست آوردن سرعت عالی ، انتخاب مناسب از عملکردهای هش ضروری است. اگر الگوریتم های هش ضعیف ساخته شوند ، میزان برخورد می تواند همچنان بزرگ باشد.

3. هشویی زنجیر شده

زنجیر کردن یک استراتژی برای جلوگیری از برخورد است. با هش زنجیره ای ، هر شکاف در جدول هش به عنوان یک گره سر برای داده ها عمل می کند ، که پس از آن درج می شود. در نتیجه ، اگر گره خالی باشد ، داده ها به گره ریشه اضافه می شوند. در عوض ، اگر داده ها از قبل وجود داشته باشند ، داده های دریافتی پس از گره سر موجود وصل یا درج می شوند. در مثال ما ، FG به عنوان یک لیست مرتبط یا "زنجیره ای" به CD اضافه می شود.

4. هشدار بسته

هشویی بسته ، که اغلب به آن آدرس دهی باز گفته می شود ، تکنیکی است که برای حل برخورد در جداول هش استفاده می شود. این رویکرد با کاوش (یا اسکن) موقعیت های متناوب در داخل آرایه (دنباله کاوشگر) تا زمانی که شاخص هدف یا یک شکاف بلااستفاده قرار داشته باشد ، برخورد هش را برطرف می کند.

این کاوشگر می تواند به شکل:

• کاوش خطی ، که در آن فاصله بین پروب ها به طور معمول در 1 واحد مشخص می شود.
• کاوش درجه دوم ، که در آن فاصله بین پروب ها به صورت چهارگانه رشد می کند (همانطور که توسط یک عملکرد درجه دوم بیان شده است).
• هشویی مضاعف ، که در آن فاصله بین پروب ها برای هر رکورد مشخص شده است اما با استفاده از الگوریتم هش دیگر ، همانطور که در بالا مورد بحث قرار گرفت ، محاسبه می شود.

توابع هشویی

یک تابع هش یک الگوریتم ریاضی است که یک مقدار ورودی عددی را فشرده می کند. طول ورودی به عملکرد هش انعطاف پذیر است ، در حالی که طول خروجی همیشه ثابت است. مقادیر هضم پیام و هش مقادیر تولید شده توسط یک الگوریتم هش است.

چند کارکرد معمولی هش عبارتند از:

1. روش تقسیم

فرض کنید یک جدول هش به اندازه «S» دارد و می خواهد یک جفت (کلید، مقدار) را در آن ثبت کند. با توجه به رویکرد تقسیم، تابع هش H(k) = کلید mod N خواهد بود. N یک عدد صحیح مثبت است که برای محاسبه مقدار هش استفاده می شود، که باید بزرگتر از S باشد. گاهی اوقات، S جایگزین N می شود، همانطور که دراین مورد.

2. روش مربع وسط

محاسبه مقدار هش به دو مرحله نیاز دارد. با یک جفت (کلید، مقدار)، یک تابع هش با محاسبه مربع کلید یا کلید*کلید محاسبه می شود. سپس کد تعدادی از ارقام را از مرکز عدد صحیح برای تولید مقدار هش انتخاب می کند.

3. روش تاشو دیجیتال

این نوع عملکرد هش شامل دو مرحله است. در ابتدا، کلید-مقدار k را پارتیشن بندی می کنیم و چندین قسمت ایجاد می کنیم: k1، k2، k3، k4، ...، kn، که در آن هر قسمت دارای تعداد یکسانی ارقام است به جز قسمت نهایی که ممکن است شامل ارقام کوتاه تری باشد. پس از این، اجزای جداگانه اضافه می شوند. مقدار هش با نادیده گرفتن انتقال قبلی، در صورت وجود، تعیین می شود.

4. روش ضرب

این نوع عملکرد برخلاف سه مرحله اول دارای چندین مرحله است.

• مقدار ثابت A را طوری انتخاب کنید که 0 کمتر از A و بزرگتر از 1 باشد.
• مقدار کلید را در A ضرب کنید.
• (k*A) mod 1 را محاسبه کنید تا قسمت کسری یا اعشاری k*A را بدست آورید.
• نتیجه مرحله قبل را در اندازه جدول هش ضرب کنید، مانند M.
• مقدار هش با گرفتن طبقه (یعنی مقدار کامل عدد صحیح به جای اعشار) نتیجه از مرحله 4 ایجاد می شود.

فرمول این تابع به این صورت است: h(K) = کف (M (kA mod 1))، که در آن h(K) کلید هش است.

بردن

هش کردن یکی از مفاهیم اساسی است که امروزه رمزنگاری و رمزگذاری را تقویت می کند. در دهه 1950 زمانی که یک مهندس IBM متوجه شد که قرار دادن تمام داده ها در یک سطل منفرد و فهرست شده، جستجو و بازیابی را بسیار سریعتر می کند، اختراع شد. امروزه، هش کردن تکنیکی است که توسط موتورهای جستجو، سرویس های ابری، و بسیاری دیگر از برنامه های کاربردی مصرف کننده و سازمانی که شامل عملیات داده ها هستند، استفاده می شود.

آیا اکنون در مورد نحوه عملکرد هش کردن کاملاً واضح هستید؟به ما بگویید در فیس بوک یک پنجره جدید باز می کند، توییتر یک پنجره جدید باز می کند، و لینکدین یک پنجره جدید باز می کند. ما از اینکه ازت خبر داشته باشیم خوشحال میشویم!

منبع تصویر: Shutterstock

بیشتر در مورد داده ها

• رمزگذاری چیست؟تعریف، کار، و انواع
• امنیت داده چیست؟تعریف، برنامه ریزی، خط مشی و بهترین شیوه ها
• مدل سازی داده چیست؟فرآیند، ابزارها و بهترین شیوه ها
• DBMS (سیستم مدیریت پایگاه داده) چیست؟تعریف، انواع، ویژگی ها و مثال ها
• رمزگذاری ابری چیست؟تعریف، اهمیت، روش ها و بهترین شیوه ها