أسس تجزئة الجداول ؟

Question

أنا مشوشة تماما عن المفاهيم الأساسية من جدول تجزئة.إذا كنت رمز تجزئة كيف يمكنني حتى تبدأ ؟ ما هو الفرق بين جدول تجزئة و عادي المصفوفة ؟

أساسا إذا كان شخص ما أجاب على هذا السؤال أعتقد أن كل الأسئلة التي قد تكون الإجابة:إذا كان لدي 100 أرقام بشكل عشوائي (مثل مفاتيح), كيف يمكنني تنفيذ جدول تجزئة و لماذا يكون من المفيد أكثر من المصفوفة ؟

الزائف رمز أو جافا سيكون موضع تقدير كأداة للتعلم...

Answer 1

إجابات حتى الآن ساعدت على تحديد الجداول التجزئة شرح بعض النظريات ولكن أعتقد على سبيل المثال قد تساعدك على الحصول على شعور أفضل بالنسبة لهم.

ما هو الفرق بين جدول تجزئة و عادي المصفوفة ؟

جدول تجزئة ومجموعة كلاهما الهياكل التي تسمح لك لتخزين واسترجاع البيانات.كلا تسمح لك لتحديد مؤشر واسترداد القيمة المرتبطة به.الفرق ، كما دانيال Spiewak الإشارة إلى أن مؤشرات صفيف متتابعة, ، في حين أن أولئك من جدول تجزئة على أساس قيمة البيانات المرتبطة بها.

لماذا يمكنني استخدام تجزئة الجدول ؟

جدول تجزئة يمكن أن توفر وسيلة فعالة جدا للبحث عن العناصر في كميات كبيرة من البيانات ، وخاصة البيانات التي لا خلاف للبحث بسهولة.("كبيرة" هنا يعني الأصلع, بمعنى أن الأمر سيستغرق وقتا طويلا لأداء متتابعة البحث).

إذا كنت رمز تجزئة كيف يمكنني حتى تبدأ ؟

لا توجد مشكلة.أبسط طريقة هي أن يخترع التعسفي الرياضية العملية التي يمكن تنفيذها على البيانات التي تقوم بإرجاع عدد N (عادة ما يكون عدد صحيح).ثم استخدام هذا العدد مؤشر إلى مجموعة من "دلاء" و تخزين البيانات الخاصة بك في دلو #N.الحيلة هي في اختيار العملية التي تميل إلى وضع القيم في دلاء مختلفة في الطريقة التي يجعل من السهل بالنسبة العثور عليها في وقت لاحق.

على سبيل المثال: مركز تجاري كبير يحتفظ بقاعدة بيانات من رعاته السيارات وقوف السيارات مواقع لمساعدة المتسوقين تذكر حيث كانت متوقفة.قاعدة بيانات مخازن make, color, license plate, ، parking location.على ترك المتجر المتسوق يجد سيارته من خلال إدخال جعل لها ولا لون.قاعدة البيانات بإرجاع (قصيرة نسبيا) قائمة من لوحات و أماكن وقوف السيارات.المسح السريع ويقع المتسوق السيارة.

هل يمكن تنفيذ هذا مع استعلام SQL:

SELECT license, location FROM cars WHERE make="$(make)" AND color="$(color)"

إذا كانت البيانات المخزنة في صفيف ، التي هي في الأساس مجرد قائمة ، يمكنك أن تتخيل تنفيذ الاستعلام من خلال مسح مجموعة لجميع مطابقة الإدخالات.

من ناحية أخرى, تخيل تجزئة القاعدة:

إضافة رموز الحرف ASCII من جميع الرسائل في جعل اللون القسمة على 100 و استخدام ما تبقى كما تجزئة القيمة.

هذه القاعدة سيتم تحويل كل عنصر إلى رقم بين 0 و 99 أساسا الفرز البيانات إلى 100 الدلاء.في كل مرة يحتاج العملاء لتحديد موقع السيارة ، يمكنك تجزئة و اللون للعثور على واحد دلو من 100 الذي يحتوي على المعلومات.لقد خفضت فورا في البحث عن طريق عامل من 100!

الآن على نطاق المثال إلى كميات ضخمة من البيانات ، ويقول قاعدة البيانات مع الملايين من الإدخالات التي يتم البحث على أساس عشرات من المعايير."جيد" تجزئة الوظيفة توزيع البيانات إلى مجموعات بطريقة تقلل إضافية في البحث عن توفير قدر كبير من الوقت.

Answer 2

أولا، عليك أن تفهم ما هي وظيفة التجزئة. ودالة البعثرة وظيفة التي تأخذ مفتاح (على سبيل المثال، سلسلة من طول arbritrary) وتقوم بإرجاع عدد <م> فريدة من نوعها ممكن . يجب على نفس المفتاح دوما بإرجاع نفس التجزئة. وظيفة سلسلة التجزئة حقا بسيطة في جاوة قد تبدو

public int stringHash(String s) {
    int h = s.length();
    for(char c : s.toCharArray()) {
        h ^= c;
    }
    return h;
}

ويمكنك دراسة وظيفة تجزئة جيدة في http://www.azillionmonkeys.com/qed/ hash.html

والآن، خريطة التجزئة تستخدم هذه قيمة التجزئة لوضع قيمة في صفيف. التبسيط طريقة جافا:

public void put(String key, Object val) {
    int hash = stringHash(s) % array.length;
    if(array[hash] == null) {
        array[hash] = new LinkedList<Entry<String, Object> >();
    }
    for(Entry e : array[hash]) {
        if(e.key.equals(key)){
            e.value = val;
            return;
        }
    }
    array[hash].add(new Entry<String, Object>(key, val));
}

و(هذه الخريطة تفرض مفاتيح فريدة من نوعها. ليست كل الخرائط القيام به.)

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

والآن للبحث عن مفتاح:

public Object get(String key) {
    int hash = stringHash(key) % array.length;
    if(array[hash] != null) {
        for(Entry e : array[hash]) {
            if(e.key.equals(key))
                return e.value;
        }
    }

    return null;
}

Answer 3

وHashtables نشعر <م> النقابي . هذا هو الفرق الهائل من المصفوفات، والتي هي هياكل البيانات فقط الخطية. مع مجموعة، قد تفعل شيئا مثل هذا:

int[] arr = ...
for (int i = 0; i < arr.length; i++) {
    System.out.println(arr[i] + 1);
}

لاحظ كيف كنت تحصل على عنصر من المصفوفة عن طريق تحديد الذاكرة الدقيقة الإزاحة (i). وهذا يتناقض مع hashtables، والتي تسمح لك لتخزين أزواج مفتاح / قيمة، في وقت لاحق استرجاع قيمة على أساس مفتاح:

Hashtable<String, Integer> table = new Hashtable<String, Integer>();
table.put("Daniel", 20);
table.put("Chris", 18);
table.put("Joseph", 16);

ومع الجدول أعلاه، يمكننا أن نجعل من المكالمة التالية:

int n = table.get("Chris");

... والتأكد من أن n سيتم بقيمة 18.

وأعتقد أن هذا ربما الإجابة على معظم الأسئلة الخاصة بك. تنفيذ جدول هاش هو موضوع مثير للاهتمام إلى حد ما، واحد الذي يتناول يكيبيديا مقبول جيد .

Answer 4

"أنا أكثر اهتماما في طريقة تجزئة الجداول البحث عن المفتاح و كيف يتم إنشاء المفتاح."

1. تجزئة تحول كائن أساسي إلى عدد.وهذا ما يسمى "تجزئة" -- يجعل تجزئة من وجوه.انظر وظيفة تجزئة.تلخيص بايت من سلسلة ، على سبيل المثال ، هو معيار تجزئة تقنية.يمكنك حساب مجموع مودولو 2³² للحفاظ على تجزئة إلى حجم معقول.تجزئة دائما يعطي نفس الجواب.هذا هو O(1).

2. عدد يمنحك "فتحة" في HashTable.نظرا التعسفي مفتاح كائن تجزئة القيمة يحسب قيمة التجزئة.تجزئة القيمة ثم يعطيك فتحة في الجدول.عادة mod( hash, table size ).هذا هو O(1) أيضا.

هذا هو الحل العام.اثنين الرقمية الحسابية و كنت قد ذهبت من التعسفي كائن مفتاح التعسفي وجوه القيمة.قليل من الأشياء يمكن أن تكون سريعة.

التحول من كائن إلى تجزئة القيمة يحدث في واحدة من هذه الطرق شيوعا.

1. إذا كانت "بدائية" كائن من 4 بايت, ثم الكائن الأصلي قيمة عدد.

2. الكائن العنوان هو 4 بايت, ثم كائن عنوان يمكن أن تستخدم تجزئة القيمة.

3. بسيطة وظيفة تجزئة (MD5, SHA1, أيا كان) يتراكم بايت من وجوه لإنشاء 4 بايت عدد.المتقدمة التجزئة ليست مبالغ بسيطة من وحدات البايت ، مبلغ بسيط لا تعكس كل المدخلات بت إلى حد ما بما فيه الكفاية.

فتحة في جدول التجزئة هو وزارة الدفاع( رقم حجم الجدول ).

لو أن فتحة القيمة المطلوبة ، أنت القيام به.إن لم يكن هذا هو المطلوب قيمة تحتاج إلى البحث في مكان آخر.هناك العديد من شعبية التحقيق خوارزميات للبحث عن بقعة خالية في الجدول.الخطية هو بحث بسيط المقبل مجانا بقعة.الدرجة الثانية هو غير الخطية التنقل في جميع أنحاء تبحث عن القمار الحرة.مولد رقم عشوائي (مع ثابت البذور) يمكن استخدامها لتوليد سلسلة من التحقيقات التي سوف تنتشر البيانات بالتساوي ولكن بشكل تعسفي.

السبر خوارزميات لا O(1).إذا كان الجدول كبيرة بما يكفي, احتمالات الاصطدام منخفضة ، تحقيقات لا يهم.إذا كان الجدول صغيرة جدا, ثم التصادم يحدث والتحقيق يحدث.عند هذه النقطة يصبح مسألة "ضبط التغيير والتبديل" لتحقيق التوازن بين التحقيق و حجم الجدول لتحسين الأداء.عادة نحن فقط جعل الجدول أكبر.

انظر جدول التجزئة.

Answer 5

وشيء لم أكن أرى وأشار تحديدا بعد:

ووجهة استخدام جدول تجزئة على مجموعة هي الأداء.

وبالتكرار عبر مجموعة واسعة من شأنه عادة يستغرق من O (1) إلى O (خ) حيث x هو عدد العناصر في المصفوفة. ولكن الوقت للعثور البند الخاص بك وسوف يكون للغاية <م> متغير ، مصممة خصيصا إذا كنا نتحدث عن مئات الآلاف من العناصر في مجموعة.

وجدول تجزئة المرجح بشكل صحيح ديه عادة ما يقرب <م> ثابت وقت وصول ما يزيد قليلا O (1)، بغض النظر عن عدد العناصر في جدول التجزئة.

Answer 6

وأنت لا تريد استخدام جدول تجزئة 100 أرقام بشكل عشوائي.

وهناك طريقة جيدة للتفكير في الجداول التجزئة هو التفكير في أزواج قيمة. دعونا نستخدم الطلاب، ويقول كل من لديه رقم هوية الطالب. في البرنامج يمكنك تخزين المعلومات على الطلاب (الأسماء وأرقام الهواتف، والفواتير، الخ). كنت تريد أن تجد كل المعلومات عن طالب باستخدام المعلومات الأساسية فقط (اسم أو الطالب ID، على سبيل المثال).

ودعونا نقول لديك 10،000 طالب. إذا قمت بتخزين كل منهم في صفيف، ثم لديك لحلقة من خلال مجموعة كاملة مقارنة هوية الطالب لكل إدخال مع واحد كنت تبحث عنه.

إذا، بدلا من ذلك، كنت "تجزئة" (انظر أدناه) رقم هوية الطالب على وظيفة في مجموعة، فإنك لا تملك إلا أن البحث أعداد الذين والطالب لها نفس التجزئة. أقل بكثير العمل على إيجاد ما تريد.

في هذا المثال، دعنا نقول معرفات الطالب ليست سوى 6 أرقام أرقام. لدينا وظيفة التجزئة يمكن فقط استخدام أسفل 3 أرقام من الرقم كما في "مفتاح الشباك". وبالتالي يتم تجزئته 232145 إلى مجموعة موقع 145. لذا فإنك تحتاج فقط مجموعة من 999 عنصر (كل عنصر كونها قائمة الطلاب).

وهذا ينبغي أن يكون بداية جيدة بالنسبة لك. يجب عليك، وبطبيعة الحال، وقراءة كتاب أو نص يكيبيديا لهذا النوع من المعلومات. ولكن أفترض أنك قد فعلت ذلك، وتعبت من القراءة.

Answer 7

وهنا هو، باختصار، كيف يعمل جدول التجزئة.

وتخيل لديك مكتبة، كاملة من الكتب. لو كنت لتخزين الكتب في مجموعة، وكنت وضعت كل كتاب على بقعة على الرف، وبعد ذلك عندما يقوم شخص ما طلب منك أن تجد كتابا، وكنت أنظر من خلال جميع الرفوف - بطيئة جدا. إذا قال أحدهم "كتاب # 12345"، التي يمكن العثور عليه بسهولة جدا، وإن كان.

ودعونا نقول بدلا من ذلك أقول لكم، إذا يبدأ عنوان الكتاب مع 'A'، فإنه يذهب في الصف 1. إذا كان الحرف الثاني هو 'B'، فإنه يذهب في الصف 1، رف 2. إذا كان الحرف الثالث هو 'C '، فإنه يذهب في الصف 1، 2 رف، والجرف 3 ... وهلم جرا حتى تتعرف على موقف الكتاب. ثم، استنادا إلى عنوان الكتاب، هل يمكن أن نعرف بالضبط أين ينبغي أن يكون.

والآن، هناك بعض المشاكل في التبسيط "تجزئة" الخوارزمية التي وصفتها - بعض الرفوف هي على وشك أن الطريق فوق طاقتها بينما يقف آخرون فارغة، سيتم تعيين بعض الكتب لنفس الفتحة .. لذلك وظائف التجزئة الحقيقية هي شيدت بعناية في محاولة لتجنب مثل هذه المشاكل.

ولكن هذه هي الفكرة الأساسية.

Answer 8

وأنا سأجيب هذا الجزء عن الفرق بين جدول تجزئة ومجموعة ... ولكن منذ ان كنت أبدا تنفيذ خوارزمية التجزئة في أي استيراد من قبل، سأترك هذا لشخص أكثر دراية:)

والمصفوفة هي مجرد قائمة مرتبة من الكائنات. الكائن نفسه لا يهم حقا ... ما هو مهم هو أنه إذا كنت ترغب في قائمة الكائنات في الترتيب من حيث الإدراج، هو دائما نفسه (وهذا يعني أن العنصر الأول <م> دائما لديه مؤشر 0).

وأما بالنسبة للجدول هاش، وهذا فهرستها من قبل مفاتيح، لا النظام ... وأعتقد أن بحث أساسي على خوارزميات التجزئة سوف تعطيك الكثير من البصيرة مما أستطيع ... ويكيبيديا لديها واحدة لائق جدا ... أن يحدد "دلو" أن مفاتيح الخوض لاسترجاع سريع على الأشياء التعسفية استخدامها كمفاتيح.

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

Answer 9

[وهذا هو الرد على تعليق أدلى به me.yahoo.com/a أعلاه]

وهذا يعتمد على وظيفة التجزئة الخاصة بك. دعونا نفترض أن دالة تجزئة بك علامات الرقم كلمة وفقا لطول كلمة الخاص بك، ومفتاح لكريس يكون 5. وبالمثل، فإن المفتاح لياهو يكون أيضا 5. الآن، على حد سواء القيم (كريس وياهو) سيذهب تحت 5 (أي في "دلو" مرتبطا بنسبة 5). بهذه الطريقة لم يكن لديك لجعل مجموعة يساوي حجم البيانات الخاصة بك.

Answer 10

والسؤال، في اعتقادي، وأجاب بكل وضوح وفي العديد من الطرق المختلفة حتى الآن.

وأود فقط أن أضيف وجهة نظر أخرى (والتي قد تخلط بين القارئ الجديد أيضا)

وعلى مستوى أقل التجريد، المصفوفات هي مجرد كتلة قريبة من الذاكرة. وبالنظر إلى عنوان البداية (startAddress)، وحجم (sizeOfElement) وindex من عنصر واحد، يتم احتساب عنوان عنصر على النحو التالي:

elementAddress = startAddress + sizeOfElement * index

والشيء المثير للاهتمام أن نلاحظ هنا أن المصفوفات يمكن أن تستخرج / ينظر إليها على أنها الجداول التجزئة مع index كمفتاح والدالة أعلاه بوصفها وظيفة التجزئة الذي يحسب موقع قيمة في <القوي> O (1)

Answer 11

وجدول تجزئة هو بنية البيانات التي تم إنشاؤها لنظرة سريعة تصل.

والجداول التجزئة ليست فعالة عندما يكون عدد الإدخالات صغيرة جدا.

إشارة

وفيما يلي بعض الأمثلة:

    import java.util.Collection;
    import java.util.Enumeration;
    import java.util.Hashtable;
    import java.util.Set;

    public class HashtableDemo {

    public static void main(String args[]) {

// Creating Hashtable for example

     Hashtable companies = new Hashtable();


// Java Hashtable example to put object into Hashtable
// put(key, value) is used to insert object into map

     companies.put("Google", "United States");
     companies.put("Nokia", "Finland");
     companies.put("Sony", "Japan");


// Java Hashtable example to get Object from Hashtable
// get(key) method is used to retrieve Objects from Hashtable

     companies.get("Google");


// Hashtable containsKey Example
// Use containsKey(Object) method to check if an Object exits as key in
// hashtable

     System.out.println("Does hashtable contains Google as key: "+companies.containsKey("Google"));


// Hashtable containsValue Example
// just like containsKey(), containsValue returns true if hashtable
// contains specified object as value

      System.out.println("Does hashtable contains Japan as value: "+companies.containsValue("Japan"));


// Hashtable enumeration Example
// hashtabl.elements() return enumeration of all hashtable values

      Enumeration enumeration = companies.elements();

      while (enumeration.hasMoreElements()) {
      System.out.println("hashtable values: "+enumeration.nextElement());
      }


// How to check if Hashtable is empty in Java
// use isEmpty method of hashtable to check emptiness of hashtable in
// Java

       System.out.println("Is companies hashtable empty: "+companies.isEmpty());


// How to find size of Hashtable in Java
// use hashtable.size() method to find size of hashtable in Java

      System.out.println("Size of hashtable in Java: " + companies.size());


// How to get all values form hashtable in Java
// you can use keySet() method to get a Set of all the keys of hashtable
// in Java

      Set hashtableKeys = companies.keySet();


// you can also get enumeration of all keys by using method keys()

      Enumeration hashtableKeysEnum = companies.keys();


// How to get all keys from hashtable in Java
// There are two ways to get all values form hashtalbe first by using
// Enumeration and second getting values ad Collection

      Enumeration hashtableValuesEnum = companies.elements();


      Collection hashtableValues = companies.values();


// Hashtable clear example
// by using clear() we can reuse an existing hashtable, it clears all
// mappings.

       companies.clear();
      }
     }

وإخراج:

Does hashtable contains Google as key: true

Does hashtable contains Japan as value: true

hashtable values: Finland

hashtable values: United States

hashtable values: Japan

Is companies hashtable empty: false

Size of hashtable in Java: 3