جدول رنگین‌کمانی
مقدمهٔ زنجیرهای درهمسازی

برای زنجیرهای هش به غیر از آنچه در اینجا ذکر شد، زنجیره درهم سازی را ببینید.
فرض کنید ما یک تابع درهم ساز کد (تابع هش کد) H و یک سری محدود از کدهای P داریم، هدف محاسبهٔ اولیه ساختار یک دیتا می‌باشد. از هر خروجی H در تابع درهم ساز داده شده می‌توان یک عنصر p در P را مانند H(P)=h پیدا کرد، یا نشان داد که عنصر p در P وجود ندارد. ساده‌ترین روش برای انجام آن، محاسبهٔ (H(P برای همهٔ pهای داخل P است. اما آن موقع ذخیره کردن جدول نیازمند (|P|n)  \theta  بیت فضا می‌باشد که در آن |P| اندازهٔ سری p و n اندازهٔ یک خروجی از H است که مانعی برای |P| بزرگ می‌باشد.
هش چین تکنیکی برای کاهش این فضای درخواست شده می‌باشد. ایدهٔ مشخص کردن یک تابع کاهشی R می‌باشد که میزان هش را به میزان ولیوها در P تقلیل دهد. به یاد داشته باشید، تابع کاهشی درواقع معکوسی از تابع درهم ساز نیست، بلکه بیشتر یک تابع متفاوت با دامنهٔ تابع و با دامنهٔ مشترک درهم ساز می‌باشد. با تناوبی کردن تابع درهم ساز با تابع کاهشی (reduction function) زنجیره‌هایی از کدهای متناوب هش ولیوهایی (یا میزانی از هش) شکل می‌گیرد. برای مثال اگر p یک سری پسوردهای شش حرفی با حروف کوچ بود و هش ولیوها ۳۲ بیتی بودند، این زنجیره به این شکل درمی‌آمد:
که تنها نیاز برای تابع کاهشی این است که بتواند یک مقدار پلین تکست را به اندازهٔ مشخصی درآورد.
برای تولید کردن جدول، ما چندین کد اولیه از P انتخاب می‌کنیم، زنجیره‌هایی از تعدادی طول k ثابت شده را در هرکدام محاسبه می‌کنیم و فقط اولین و آخرین کد در هر زنجیره را ذخیره می‌کنیم. اولین کد نقطهٔ شروع و آخرین کد نقطهٔ پایان نامیده می‌شود. برای مثال زنجیرهٔ “aaaaaa” نقطهٔ شروع می‌شود و “kiebgt” نقطه پایان و هیچ‌کدام از کدهای دیگر (یا هش ولیوها) ذخیره نمی‌شوند.
حال هش ولیوی داده شدهٔ h را می‌خواهیم معکوس کنیم (کد مطابق آن را برایش پیدا کنیم) یک زنجیره را که با h شروع می‌شود، با اعمال R، سپس H، سپس R و … محاسبه می‌کنیم اگر در هر نقطه یک ولیو (مقدار) مطابق با یکی از نقاط پایان مشاهده کنیم، نقطه شروع متناظر را نیز می‌گیرم و از آن استفاده می‌کنیم تا زنجیره را بازسازی کنیم. احتمال زیادی وجود دارد که این زنجیره شامل ولیوی h باشد، در این صورت مستقیماً ولیوی ماقبل آن در چین سیفر p می‌باشد، که ما بدنبال آن هستیم.
برای مثال اگر به ما هش 920EC10 داده شده باشد، ما زنجیرهٔ آن را با اعمال اولیه R محاسبه می‌کنیم:
{\mathtt {920ECF10}}\,{\xrightarrow[{\;R\;}]{}}\,{\color {Violet}{\mathtt {kiebgt}}}
چون “KIEBGT” یکی از نقاط پایان در جدول ما می‌باشد، ما کد متناظر شروع کنندهٔ “aaaaaa” را برمی‌داریم و زنجیرهٔ آن را دنبال می‌کنیم تا به 920ECF10 برسیم:
{\color {Red}{\mathtt {aaaaaa}}}\,{\xrightarrow[{\;H\;}]{}}\,{\mathtt {281DAF40}}\,{\xrightarrow[{\;R\;}]{}}\,{\mathtt {sgfnyd}}\,{\xrightarrow[{\;H\;}]{}}\,{\mathtt {920ECF10}}
بنابراین کد (پسورد) SGFNYD (یا هر پسوردی دیگری که هش ولیوی یکسانی دارد) می‌باشد. به یاد داشته باشید که این زنجیره همیشه شامل هش ولیوی h نمی‌باشد؛ حتی ممکن است زنجیره ای که با h شروع شده با زنجیره ای که نقطهٔ شروع متفاوتی دارد ادغام شود. برای مثال ممکن است به ما هش ولیوی FB107E70 داده شده باشد و وقتی زنجیرهٔ آن را دنبال می‌کنیم به KEIBGT برسیم:
{\mathtt {FB107E70}}\,{\xrightarrow[{\;R\;}]{}}\,{\mathtt {bvtdll}}\,{\xrightarrow[{\;H\;}]{}}\,{\mathtt {0EE80890}}\,{\xrightarrow[{\;R\;}]{}}\,{\color {Violet}{\mathtt {kiebgt}}}
اما FB107E70 زنجیره ای نیست که با “aaaaaa” شروع شود، که به این اخطار غلط (فالس آلارم) گفته می‌شود. در این حالت ما آن تطابق را رد می‌کنیم و به گسترش زنجیرهٔ h به جستجوی تطابق (مچ) دیگری می‌پردازیم. اگر زنجیرهٔ h به اندازهٔ طول زنجیرهٔ k بدون هیچ تطابق (مچ) مناسبی گسترش پیدا کرد، به این نتیجه می‌رسیم که پسورد (کد) مورد نظر در هیچ‌کدام از زنجیره‌ها تولید نشده‌است.
محتوای جدول به هش ولیو بستگی ندارد که بخواهد معکوس شود، این محتوا یکبار تولید می‌شود و سپس برای جستجوهای اصلاح نشده تکرار می‌شود. افزایش طول زنجیره اندازهٔ جدول را کاهش می‌دهد، این همچنان زمان مورد نیاز برای اجرای جستجوها را افزایش می‌دهد، این همان تبادل زمان-حافظهٔ جدول رنگین کمانی می‌باشد. در یک حالت ساده از زنجیره‌های تک موردی (تک آیتمی) جستجو بسیار سریع ولی جدول نیز بسیار بزرگ است. زمانی که زنجیره‌ها بلندتر شوند جستجو کندتر می‌شود، ولی اندازهٔ جدول کاهش می‌یابد.
هش چین‌های ساده چندین نقص دارند، جدی‌ترین آن‌ها این است، که اگر در هر نقطه ای دو زنجیره برخورد کنند (یعنی هردو ولیوی یکسانی تولید کنند) آن‌ها ادغام می‌شوند و در نتیجه جدول کد (پسورد)های زیادی را با وجود پرداخت هزینه محاسباتی یکسان، پوشش نمی‌دهد؛ زیرا زنجیره‌های قبلی کاملاً آنجا ذخیره نگشته‌اند و پیدا شدن تشخیص درست در این حالت غیرممکن است. برای مثال، اگر سومین ولیو در زنجیره ۳ با دومین ولیو در زمینهٔ ۷ تطابق داشته باشد، آن دو زنجیره تقریباً توالی یکسانی از ولیوها را پوشش می‌دهند، اما ولیوی آخر آن‌ها یکسان نخواهد بود. تابع درهم ساز H بعید است که برخوردی داشته باشد، با توجه به اینکه اتفاق نیفتادن آن یک ویژگی مهم برای ایمنی تابع محسوب می‌شود. اما تابع کاهشی R به دلیل لزومش بر درست پوشش دادن پلین تکست‌های مشابه، نمی‌تواند برای ایجاد نشدن برخورد از خود مقاومتی نشان دهد.
دیگر مشکلات منتج شده برای اهمیت انتخاب تابع مناسب برای R است.انتخاب R برای اینکه هویت آن را تشکیل دهد کمی از یک تلاش بروت فورس بهتر است. تنها زمانیکه مهاجم ایدهٔ خوبی دربارهٔ اینکه پلین تکست به چه صورت خواهد بود داشته باشد، می‌تواند یک تابع R انتخاب کند و مطئن شود که زمان و فضا تنها برای پلین تکست‌های مشابه مصرف می‌شوند، تمام فضای کدهای محتمل نیز استفاده نمی‌شوند. در اصل R نتایج اولین هش محاسباتی را به سمت مشابهی به پلین تکست‌ها هدایت می‌کند، اما این مزایا به شکلی ایجاد می‌شوند که R تقریباً همهٔ پلین تکست‌های ممکن را تولید نمی‌کند. در رده ای که مهاجم ترجیح می‌دهد آن را چک کند، انکار کردن قطعیت مهاجم نسبت به اینکه هیچ کدی از ردهٔ آن‌ها وارد نشده. همچنین طراحی تابع R بگونه ای که با پلین تکست‌های مورد انتظار تطابق داشته باشد می‌تواند سخت باشد.