جدول تلبيد

جدول هاش
معلومات عامة
صنف فرعي من
البداية
1953 عدل القيمة على Wikidata
زمن الاكتشاف أو الاختراع
1953 عدل القيمة على Wikidata

تعديل - تعديل مصدري - تعديل ويكي بياناتحول القالب

جدول تلبيد (بالإنجليزية: Hash table)‏ هو أحد بنى البيانات في علم الحاسوب يملك خصائص المصفوفات الترابطية، يستخدم لإسناد قيمة إلى مفتاح ما في ذاكرة الحاسب. والبحث عن قيم محددة بسرعة كبيرة مقارنة ببنى المعطيات الأخرى. يستعمل جدول التقطيع، تابع تقطيع يمكنه من حساب مكان القيمة في لائحة المفاتيح.

في الحالة المثالية، يفترض بجدول التلبيد، ربط كل مفتاح بحجرة معينة، ولكن في الواقع ذلك يجعل زمن البحث فيه عن القيم المتضاربة كبيراً جداً، لذلك تم إيجاد عدة حلول ونماذج لجداول التلبيد يُفترض فيها وجود قيم متضاربة على حساب تخفيض زمن البحث.

جداول التلبيد ذات العنونة المباشرة (المفتوحة)

العنونة المباشرة هي طريقة بسيطة التي تعمل كما يجب عندما المجموعة الكلية للمفاتيح U تكون صغيرة نسبيا لنفترض انه لتطبيق معين طلب مجموعة ديناميكية حيث ان لكل فرد في المجموعة أخذ مفتاح من {U={1,2,3,...,m-1 عندما m ليس عددا ضخما سنفترض أن المفاتيح المأخوذة مختلفة تماما. جدول العنونة سنطبقها بواسطة مصطفة أي جداول العنونة مباشرة (directed adress table) سيكون [T[0,...,m-1 وكل مكان في الجدول يسمى خلية أو slot الذي يلائم مفتاحا من المجموعة الكلية إذا الجدول لم يحوِ أيّ مفتاح قيمته k حينها [nil=T[k 

direct-adress-search(T,k)
return T[k]
Direct-adress-insert(T,x)
   T[key[x]]<-x
Direct-adress-delete(T,x)
T[key[x]]<-NIL

كل الخوارزميات في الأعلى سريعة وفعالة حيث ان كل منها يقوم بعدد قليل من العمليات (O(1

جداول هاش

الصعوبة في جداول العنونة المباشرة هي كبر المجموعة U حيث ان القيام بحفظ مصفوفة بحجم |U| غير واقعي وغير تطبيقي ومن ناحية أخرى قد تكون المجموعة K صغيرة كثيرا بالنسبة ل-U وعندها أغلب الأماكن في U ستكون حتما غير نافعة. عندما تكون المجموعة K (القاموس) صغيرة جدا بالنسبة ل-U جدول هاش سيتطلب مكان اقل من جداول عنونة مباشرة أي سيتطلب جدول هاش (|O(|K بالرغم من أن بحث قيمة معينة في الجدول سيكون أيضا (O(1 المشكلة الوحيدة هو ان البحث في جدول الهاش هو متوقع بينما في العنونة المباشرة البحث هو (O(1 دائما بالعنونة المباشرة حفظنا المفتاح k في الخلية k اما في الهاش فهذا المفتاح سوف يحفظ في (h(k أي اننا سوف نستخدم دالة هاش (hash function) لحساب الخلية التي سنحفظ فيها المفتاح k، 

h:U->{0,1,...,m-1}

نقول ان المفتاح k منقول (hashes)للخلية (h(k ; أي انه (h(k يسمى قيمة الهاش (hash value). مشكلة من نوع اخر تظهر في الهاش وهي عندما يكون هناك مفتاحان k,t قيم الهاش خاصتهما متشابه أي: (h(t)=h(k تسمى هذه الظاهرة بالتشابك في جدول الهاش أو collision ولهذه المشكلة يوجد حلول جيدة وفعالة. قد يتبادر إلى الذهن حل عن طريق جعل h دالة عشوائية وساعتها سيكون هنالك اقل تشابك ولكن هذا الحل ليس طبيعي لأننا نريد الدالة h قطعية (deterministic) الطريقة الأفضل لحل هذه المشكلة هي السلسلة (chaining) وهناك طريقة أخرى وهي العنونة المفتوحة (open addressing)

حل مشكلة التشابك على طريق السلسلة

في طريقة السلسلة (chaining) كل التشابكات في نفس الخلية نسلسلها بواسطة سلسلة عند حل التشابكات بواسطة السلسلة من السهل ان نطبق عمليات الجدول T 

Chained-hash-Insert(T,x)
enter x in the haed of T[h(key(x))]
chained-hash-search(T,k)
search item with key value k in the list of T[h(k)]
chained-hash-delete(T,x)
delete x from T[h(key(x))]

عملية الإدخال تتم ب-(O(1 وقت اما البحث ففي الحالة الأسوأ يكون البحث (|[[O(|T[h[key ولكن في حالات الوسط يكون (O(1 اما الحذف (O(1 عندما تكون السلسلة ذو اتجاهين اما إذا كانت ذو اتجاه واحد عندها سيتطلب منا البحث اولا من ثم الحذف أي انه سيتطلب وقتا كما في البحث

تحليل الهاش مع سلسلة

عند إعطاءنا جدول T hg الذي يحوي على m خلايا و n قيم نعرف مقدم الكثافة(load factor) الخاص ب-T أو a=n/m أي معدل القيم المحفوظة في السلسلة الواحدة في السيناريو الأسوأ فعالية الهاش مع سلسلة جدا سيئة : كل n المفاتيح موزعين لنفس الخلية ونكون سلسلة طويلة جدا والبحث عندها سيكون (O(n +الوقت المطلوب لحساب دالة الهاش وهو ليس بأفضل من البحث في سلاسل عادية اما في السيناريو الوسط فعالية الهاش تقاس بمدى توزيع الدالة h للقيم بين المفاتيح سنفترض ان التوزيع سيكون بالتساوي أي ان الاحتمال بان قيمة معينة تذهب إلى مفتاح متساوية بين كل المفاتيح وكذلك سنفترض ان حساب دالة الهاش هو (O(1 قانون : في جدول هاش مع سلسلة فيه التوزيع متساو لكل المفاتيح بحث فاشل يقوم ب-(O(1+a فعاليات (وقت الفعالية) اثبات : بما ان التوزيع متساو لكل المفاتيح الاحتمال بان مفتاح K يذهب لخلية معينة متساو لكل الخلايا (m خلايا) لذا الوقت المتوسط للبحث الفاشل عن k مساو تماما للوقت المتوسط لبحث أحد السلاسل والطول المتوقع لسلسلة كهذه هو مقدم الكثافة أو a أي ان وقت البحث المتوسط هو a ومع حساب دالة الهاش : الوقت المتوقع هو : (O(1+a. قانون : في جدول هاش مع تشابك وفي الجدول التوزيع للمفاتيح متساو, بحث ناجح متوسط وقت البحث هو: (O(1+a. ومن القانونين في الأعلى نستنتج ان كبر الجدول يجب أن يكون مشابها لعدد القيم المراد تخزينها أي بحالة وجود (O(n قيم عندها كبر الجدول هو (O(n وعندها تكون العلمليات كل واحد منها تنفذ ب-(O(1 وقت

دوال هاش

المقالة الرئيسة: دالة تجزئة

هنالك عدة حالات بناء على المعلومات التي لدينا عن التوزيع:[1]

  1. إذا كان التوزيع معطى أي انه لكل مفتاح عندها:(h(k)=floor(km
في الحالات الأخرى وعند الافتراض ان المفاتيح ارقام طبيعية نستطيع استخدام الطرق التالية :
  1. * طريقة القسمة أي: h(k)=m mod k
  2. * طريقة الضرب أي: ((h(k)=(floor(m(1 kA mod عندما: A بين 0 و 1

مراجع

  1. ^ خضر مصباح إسماعيل (1 يناير 2010). أساسيات أمن المعلومات والحاسوب. Al Manhal. ISBN:9796500012308. مؤرشف من الأصل في 2020-07-12.

Read other articles:

Grant Holt

Grant Holt Holt bermain untuk Norwich City pada tahun 2010Informasi pribadiNama lengkap Grant HoltTanggal lahir 12 April 1981 (umur 42)Tempat lahir Carlisle, InggrisTinggi 1,83 m (6 ft 0 in)Posisi bermain PenyerangInformasi klubKlub saat ini Wigan AthleticNomor 42Karier junior Carlisle UnitedKarier senior*Tahun Tim Tampil (Gol)1999 Workington ? (?)1999–2001 Halifax Town 6 (0)2001 → Sorrento (pinjaman) ? (?)2001 → Barrow (pinjaman) ? (?)2001 Sengkang Marine ? (?)2001...

 

Cathédrale Notre-Dame-de-l'Assomption de Gozo

Cette cathédrale ne doit pas être confondue avec une autre cathédrale de Malte. D’autres cathédrales portent le nom de cathédrale Notre-Dame-de-l'Assomption. Cathédrale de Gozo Cathédrale de Gozo Présentation Nom local Knisja Katidrali ta' Għawdex Culte Catholicisme Type Cathédrale Début de la construction 1697 Fin des travaux 1711 Architecte Lorenzo Gafa Style dominant baroque maltais Site web www.gozocathedral.org Géographie Pays Malte Région Gozo Ville Rabat - Victoria...

 

Хагалаз

Буквы со сходным начертанием: N · Ν Буквы со сходным начертанием: H · Η · Н · н · ዘ · ਮ НазваниеПра-германскоеДревне-английскоеДревне-скандинавское*Hag(a)lazHægl Hagall«град»ФормаСтаршийфутаркФуторкМладшийфутарк Unicodeᚺ U+16BAᚻ U+16BBᚼ U+16BC...

World on Fire (Sarah McLachlan song)

Single by Sarah McLachlan World on FireSingle by Sarah McLachlanfrom the album Afterglow ReleasedJune 14, 2004 (2004-06-14)GenrePopLabel Nettwerk Arista Songwriter(s) Sarah McLachlan Pierre Marchand Producer(s)Pierre MarchandSarah McLachlan singles chronology Stupid (2004) World on Fire (2004) U Want Me 2 (2008) World on Fire is a song by Canadian singer-songwriter Sarah McLachlan. It was released in June 2004 as the third single from her Afterglow album (2003). Background and ...

 

Professor X

Professor XKarya seni interior Professor X dari X-Men vol. 2 (11 Agustus 1992).Seni oleh Jim Lee.Informasi publikasiPenerbitMarvel ComicsPenampilan pertamaThe X-Men #1 (September 1963)Dibuat olehStan Lee (Penulis)Jack Kirby (Ilustrasi)Informasi dalam ceritaAlter egoCharles Francis XavierSpesiesManusia mutanAfiliasi timX-MenIlluminatiNama alias terkenalOnslaught, Consort-Royal, Founder, Doctor X, Warlord, Entity, Prisoner M-13Kemampuan Genius Kemampuan telepati dengan jangkaun luas Membaca pik...

 

Sofiane Feghouli

Sofiane Feghouli Feghouli dengan timnas Aljazair pada 2014Informasi pribadiNama lengkap Sofiane FeghouliTanggal lahir 26 Desember 1989 (umur 34)Tempat lahir Levallois-Perret, PrancisTinggi 1,78 m (5 ft 10 in)Posisi bermain Gelandang serangInformasi klubKlub saat ini Fatih KaragümrükNomor 8Karier junior1998–2003 Red Star Paris2003–2004 Paris FC2004–2007 GrenobleKarier senior*Tahun Tim Tampil (Gol)2007–2010 Grenoble 60 (3)2010–2016 Valencia 146 (20)2011 → Alme...

Malta at the 1928 Summer Olympics

Sporting event delegationMalta at the1928 Summer OlympicsIOC codeMLTNOCMalta Olympic CommitteeWebsitewww.nocmalta.orgin AmsterdamCompetitors9 in 1 sportMedals Gold 0 Silver 0 Bronze 0 Total 0 Summer Olympics appearances (overview)19281932193619481952–195619601964196819721976198019841988199219962000200420082012201620202024 Malta competed in the Summer Olympic Games for the first time at the 1928 Summer Olympics in Amsterdam, Netherlands. Nine water polo players represented Malta.[1]...

 

Torcia Umana

Disambiguazione – Se stai cercando il personaggio della Golden Age, vedi Torcia Umana (originale). Disambiguazione – Human Torch rimanda qui. Se stai cercando la serie pubblicata dalla Timely Comics, vedi The Human Torch. Torcia UmanaLa Torcia Umana, disegnato da Alex Ross UniversoUniverso Marvel Nome orig.Human Torch AutoriStan Lee Jack Kirby EditoreMarvel Comics 1ª app. inFantastic Four n. 1 (novembre 1961) 1ª app. it. inLinus Estate giugno 1966, supplemento al n...

 

Daftar kecamatan dan kelurahan di Kabupaten Tulang Bawang Barat

Peta Lokasi Kabupaten Tulang Bawang Barat di Lampung Berikut ini adalah daftar kecamatan dan kelurahan/desa di kabupaten Tulang Bawang Barat, Provinsi Lampung, Indonesia. Kabupaten Tulang Bawang Barat terdiri dari 9 kecamatan, 3 kelurahan, dan 93 tiyuh (desa). Pada tahun 2017, jumlah penduduknya mencapai 268.119 jiwa dengan luas wilayah 1.201,00 km² dan sebaran penduduk 223 jiwa/km².[1][2] Daftar kecamatan dan kelurahan di Kabupaten Tulang Bawang Barat, adalah sebagai beriku...

Discrimination based on skin tone

Form of prejudice or discrimination Part of a series onDiscrimination Forms Institutional Structural Statistical Taste-based Attributes Age Caste Class Dialect Disability Genetic Hair texture Height Language Looks Mental disorder Race / Ethnicity Skin color Scientific racism Rank Sex Sexual orientation Species Size Viewpoint Social Arophobia Acephobia Adultism Anti-albinism Anti-autism Anti-homelessness Anti-drug addicts Anti-intellectualism Anti-intersex Anti-left handedness Anti-Ma...

 

AVROTROS

JenisPenyiaran publikNegaraBelandaJangkauanBelandaDidirikan7 September 2014 (1927/1965)SloganThuis bij AVROTROS(At Home with AVROTROS)Tokoh pentingEd Nijpels (ketua)Situs resmiwww.avrotros.nl AVROTROS adalah sebuah penyiaran radio dan televisi Belanda, yang bermula dari tahun 1927. AVROTROS dibentuk pada 2014 dari penggabungan para pendahulunya AVRO dan TROS. Dari 1 Januari 2014, nama penyiaran gabungan tersebut dipakai dalam program-program bersama; sejak 7 September 2014, seluruh program ya...

 

List of tallest buildings in Philadelphia

The Philadelphia skyline as seen from Boathouse Row in June 2019 (annotated version) The Philadelphia skyline as seen from the Delaware River in February 2023 Philadelphia, the largest city in the U.S. state of Pennsylvania, is home to more than 300 completed high-rise buildings up to 330 feet (101 m),[1] and 58 completed skyscrapers of 330 feet (101 m) or taller,[2] of which 34 are 400 feet (122 m) or taller and are listed below. As of 2018[update]...

Samuel Alito

US Supreme Court justice since 2006 (born 1950) The neutrality of this article is disputed. Relevant discussion may be found on the talk page. Please do not remove this message until conditions to do so are met. (June 2024) (Learn how and when to remove this message) Samuel AlitoOfficial portrait, 2007Associate Justice of the Supreme Court of the United StatesIncumbentAssumed office January 31, 2006Appointed byGeorge W. BushPreceded bySandra Day O'ConnorJudge of the United States Court of...

 

United States support for Iraq during the Iran–Iraq War

Iraqgate redirects here. For other uses, see Iraqgate (disambiguation). Bilateral relations Iraq United States United States support for Ba'athist Iraq during the Iran–Iraq War, in which it fought against post-revolutionary Iran, included several billion dollars' worth of economic aid, the sale of dual-use technology, military intelligence, and special operations training.[1][2] The U.S. refused to sell arms to Iraq directly due to Iraq's ties to Palestinian groups which the...

 

Kwantung Leased Territory

Japanese concession in northern China in 1895 and from 1905 to 1945 Kwantung redirects here. For the army group of the Imperial Japanese Army, see Kwantung Army. Not to be confused with Kwangtung. Kwantung Leased Territory關東州1905–1945 Flag(1905–1945) Crest Anthem: KimigayoKwantung Leased Territory in 1921 including the Japanese area of influence and neutral zone.StatusLeased territory (colony) of the Empire of JapanCapitalDalianGovernor • 1905–1912 (first) Ōshima...

Kurumali River

Dawn at Kurumaly river Kurumali river. View from Railway bridge near Pudukkad The Kurumali River is a major tributary of the Karuvannur River in the Thrissur district of Kerala. It originates in the Western Ghats in the Chimmony Wildlife Sanctuary of Thrissur District. Course The Kurumali River has its origin on the slopes of the Western Ghats in the Chimmony Wildlife Sanctuary of the Thrissur district. The Chimmony dam is built across the Kurumali River. The Muply River joins the Kurumali r...

 

Al-Awasim

al-Thughur redirects here. For the frontiers of Islamic Spain, see Upper March, Central March, and Lower March. Muslim fortifications Thughur and Awasimاَلـثُّـغُـوْر وَالْـعَـوَاصِـمal-thughūr wa-l-ʿawāṣimCilicia, northern Syria and Upper Mesopotamia TypeFortified border zoneSite informationControlled byAbbasid Caliphate (750s–c. 930), Ikhshidids (c. 935–940s), Hamdanids (940s–962s), Mamluks of Egypt (14th century–1516)Site historyB...

 

Bedfordshire Yeomanry

Bedfordshire YeomanryActive1797–18101817–18271901–2014Country Kingdom of Great Britain (1797–1800) United Kingdom (1801–2014)Branch British ArmyTypeYeomanrySizeRegimentPart ofYeomanry (First World War)Royal Artillery (Second World War)Garrison/HQBedfordEngagementsFirst World War France and Flanders 1915-18 Second World War No battle honours were awarded. It is tradition within artillery units that the Regiment's guns represent its colours and battle honours. Mili...

費莉達·古斯塔夫臣

費莉達·古斯塔夫臣Frida Gustavsson 在2010年的Max Azria跑道。模特儿英文名Frida Gustavsson国籍 瑞典出生 (1993-06-06) 1993年6月6日（31歲） 瑞典斯德哥尔摩职业模特兒配偶Hjalmar Rechlin（2015年结婚—2017年结束）Marcel Engdale（2022年结婚）活跃年代2009年至今经纪公司 美国 英国 義大利 法國IMG Models 費莉達·古斯塔夫臣或芙丽达·古斯塔夫松（Frida Gustavsson；1993年6月6日—...

 

J-pop

La información de este artículo tiene relación con la música de Japón. Por favor, si ves aquí el título o artista de una canción que a tu juicio sea irregular (generalmente errores ortográficos de mayúsculas y minúsculas, o inclusión de caracteres gráficos), déjalo de esta forma, ya que lo más probable es que así sea como se escriba oficialmente. J-popOrígenes musicales Dance-pop, Kayōkyoku, eurobeat, EDM, Pop, electropop, Minimal techno, EuropopOrígenes culturales Japón ...