ios - كيفية تطبيق بروتوكول Hashable في سويفت لصفيف Int(بنية سلسلة مخصصة)

arrays string (3)

أقوم بإنشاء هيكل يعمل String ، إلا أنه لا يتعامل إلا مع القيم العددية Unicode UTF-32. وبالتالي ، هو مجموعة من UInt32 . (انظر هذا السؤال لمزيد من المعلومات الأساسية.)

ما أريد القيام به

أريد أن أكون قادرًا على استخدام بنية ScalarString المخصصة الخاصة بي كمفتاح في القاموس. فمثلا:

var suffixDictionary = [ScalarString: ScalarString]() // Unicode key, rendered glyph value

// populate dictionary
suffixDictionary[keyScalarString] = valueScalarString
// ...

// check if dictionary contains Unicode scalar string key
if let renderedSuffix = suffixDictionary[unicodeScalarString] {
    // do something with value
}

مشكلة

للقيام بذلك ، تحتاج ScalarString إلى تنفيذ البروتوكول Hashable . اعتقدت أنني سأكون قادرًا على فعل شيء مثل هذا:

struct ScalarString: Hashable {

    private var scalarArray: [UInt32] = []

    var hashValue : Int {
        get {
            return self.scalarArray.hashValue // error
        }
    }
}

func ==(left: ScalarString, right: ScalarString) -> Bool {
    return left.hashValue == right.hashValue
}

ولكن بعد ذلك اكتشفت أن صفيفات سويفت لا تحتوي على hashValue .

ما قرأت

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

خاصية الكائن (الصفيف لا يحتوي hashValue )
خاصية معرّف الهوية (غير متأكد من كيفية تنفيذها بشكل جيد)
الصيغة (يبدو أن أي صيغة لسلسلة من أعداد صحيحة 32 بت ستكون ثقيلة للمعالج ولديها الكثير من تجاوز عدد صحيح)
ObjectIdentifier (أنا أستخدم بنية ، وليس فئة)
وراثة من NSObject (أنا أستخدم بنية ، وليس فئة)

إليك بعض الأشياء الأخرى التي قرأتها:

سؤال

تحتوي Swift Strings على خاصية hashValue ، لذلك أعرف أنه من الممكن القيام بذلك.

كيف يمكنني إنشاء hashValue للهيكل المخصص الخاص بي؟

التحديثات

التحديث 1: أود أن أفعل شيئًا لا يتضمن التحويل إلى String ثم استخدام hashValue . كانت وجهة نظري بأكملها لإنشاء بنائي الخاص حتى أتمكن من تجنب إجراء الكثير من تحويلات String . String يحصل انها hashValue من مكان ما. يبدو أنني يمكن أن تحصل عليه باستخدام نفس الطريقة.

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

جافا خوارزمية خوارزمية
خوارزميات C
دالة التجزئة للسلسلة (سؤال وجواب SO في C)
برنامج تعليمي عن هاش (مجموعة أبحاث تقنيات الخوارزمية في فرجينيا تك)
خوارزميات دالة التجزئة للأغراض العامة

تحديث 3

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

قدمت حلاً ممكنًا باستخدام وظيفة تجزئة DJB.

تحديث

writes مارتن آر:

اعتبارًا من Swift 4.1 ، يمكن Equatable التحويل البرمجي تجميع Equatable و Hashable لأنواع المطابقة تلقائيًا ، إذا كان جميع الأعضاء يتوافقون مع Equatable / Hashable (SE0185). واعتبارًا من Swift 4.2 ، تم دمج أداة تجزئة ذات جودة عالية في مكتبة Swift القياسية (SE-0206).

لذلك لم تعد هناك حاجة لتحديد وظيفة التجزئة الخاصة بك ، يكفي الإعلان عن المطابقة:
struct ScalarString: Hashable, ... {

    private var scalarArray: [UInt32] = []

    // ... }

وبالتالي ، يجب إعادة كتابة الإجابة أدناه (مرة أخرى). حتى يحدث ذلك ، راجع إجابة Martin R من الرابط أعلاه.

الجواب القديم:

تمت إعادة كتابة هذه الإجابة بالكامل بعد تقديم إجابتي الأصلية لمراجعة الرمز .

كيفية التنفيذ لبروتوكول Hashable

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

تنفيذ بروتوكول Equatable (قابلية الوصل القابلة للتداول من Equatable)
إرجاع hashValue محسوبة

هذه النقاط تتبع من البديهية الواردة في الوثائق:

x == y إلى x.hashValue == y.hashValue

حيث x و y قيمتان لبعض الأنواع.

تطبيق بروتوكول Equatable

من أجل تطبيق بروتوكول Equatable ، يمكنك تحديد كيفية استخدام النوع الخاص بك لعامل التشغيل == (التكافؤ). في المثال الخاص بك ، يمكن تحديد التكافؤ مثل هذا:

func ==(left: ScalarString, right: ScalarString) -> Bool {
    return left.scalarArray == right.scalarArray
}

الدالة == عالمية بحيث تخرج عن صفك أو هيكلك.

إرجاع `hashValue` محسوبة

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

هناك عدد من الطرق لحساب قيمة التجزئة. على سبيل المثال ، يمكنك القيام بشيء بسيط مثل إرجاع عدد العناصر في الصفيف.

var hashValue: Int {
    return self.scalarArray.count
}

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

DJB هاش وظيفة

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

تطبيق سويفت writes يلي:

var hashValue: Int {
    return self.scalarArray.reduce(5381) {
        ($0 << 5) &+ $0 &+ Int($1)
    }
}

هذه نسخة محسّنة من تطبيقي الأصلي ، لكن اسمحوا لي أيضًا أن أدرج النموذج القديم الموسع ، والذي قد يكون أكثر قابلية للقراءة للأشخاص الذين ليس لديهم دراية reduce . هذا معادل ، وأعتقد:

var hashValue: Int {

    // DJB Hash Function
    var hash = 5381

    for(var i = 0; i < self.scalarArray.count; i++)
    {
        hash = ((hash << 5) &+ hash) &+ Int(self.scalarArray[i])
    }

    return hash
}

يسمح عامل التشغيل &+ Int بالتجاوز والبدء من جديد للسلاسل الطويلة.

الصورة الكبيرة

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

// Include the Hashable keyword after the class/struct name
struct ScalarString: Hashable {

    private var scalarArray: [UInt32] = []

    // required var for the Hashable protocol
    var hashValue: Int {
        // DJB hash function
        return self.scalarArray.reduce(5381) {
            ($0 << 5) &+ $0 &+ Int($1)
        }
    }
}

// required function for the Equatable protocol, which Hashable inheirits from
func ==(left: ScalarString, right: ScalarString) -> Bool {
    return left.scalarArray == right.scalarArray
}

قراءة مفيدة أخرى

قروض

شكراً جزيلاً لمارتن آر على كود في مراجعة. تستند كتابتي إلى حد كبير على writes . إذا وجدت هذا مفيدًا ، فيرجى إعطائه صوتًا لصالحه.

تحديث

Swift مفتوح المصدر الآن ، لذلك من الممكن أن نرى كيف يتم تطبيق hashValue على String من الكود المصدري . يبدو الأمر أكثر تعقيدًا من الإجابة التي قدمتها هنا ، ولم أستغل الوقت الكافي لتحليلها بشكل كامل. لا تتردد في القيام بذلك بنفسك.

أحد الاقتراحات - بما أنك تقوم بنمذجة String ، فهل ستعمل على تحويل [UInt32] إلى String واستخدام String hashValue ؟ مثله:

var hashValue : Int {
    get {
        return String(self.scalarArray.map { UnicodeScalar($0) }).hashValue
    }
}

قد يسمح لك ذلك بسهولة بمقارنة struct المخصص مع String s أيضًا ، على الرغم من أن فكرة جيدة أو لا تعتمد على ما تحاول القيام به ...

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

لذلك أفترض أنه إذا كنت تريد أن تمثل hashValue String فريدة من نوعها ، فإن hashValue ستكون جيدة. إذا كنت تريد أن تمثل hashValue تسلسلًا فريدًا من قيم UInt32 ، فإن إجابة @ Kametrixom هي السبيل للذهاب ...

تحرير (31 مايو '17): يرجى الرجوع إلى الإجابة المقبولة. هذه الإجابة هي مجرد عرض توضيحي حول كيفية استخدام CommonCrypto Framework

حسنًا ، تقدمت ووسعت كل الصفائف مع بروتوكول Hashable باستخدام خوارزمية التجزئة SHA-256 من إطار CommonCrypto. عليك أن تضع

#import <CommonCrypto/CommonDigest.h>

في رأس سد الخاص بك لهذا العمل. إنه لأمر مخز أن المؤشرات يجب أن تستخدم على الرغم من:

extension Array : Hashable, Equatable {
    public var hashValue : Int {
        var hash = [Int](count: Int(CC_SHA256_DIGEST_LENGTH) / sizeof(Int), repeatedValue: 0)
        withUnsafeBufferPointer { ptr in
            hash.withUnsafeMutableBufferPointer { (inout hPtr: UnsafeMutableBufferPointer<Int>) -> Void in
                CC_SHA256(UnsafePointer<Void>(ptr.baseAddress), CC_LONG(count * sizeof(Element)), UnsafeMutablePointer<UInt8>(hPtr.baseAddress))
            }
        }

        return hash[0]
    }
}

تحرير (31 مايو '17): لا تفعل هذا ، على الرغم من أن SHA256 ليس له أي تصادم بعثرة ، إنها فكرة خاطئة لتعريف المساواة عن طريق المساواة بالتجزئة

public func ==<T>(lhs: [T], rhs: [T]) -> Bool {
    return lhs.hashValue == rhs.hashValue
}

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

تحرير (15 يوليو 15): لقد أجريت للتو بعض اختبارات السرعة:

شغل بشكل عشوائي صفائف Int من حجم ن استغرق في المتوسط أكثر من 1000 أشواط

n      -> time
1000   -> 0.000037 s
10000  -> 0.000379 s
100000 -> 0.003402 s

بينما باستخدام طريقة تجزئة السلسلة:

n      -> time
1000   -> 0.001359 s
10000  -> 0.011036 s
100000 -> 0.122177 s

وبالتالي فإن طريقة SHA-256 أسرع بنحو 33 مرة من طريقة السلسلة. لا أقول إن استخدام السلسلة يعد حلاً جيدًا للغاية ، لكنه الحل الوحيد الذي يمكننا مقارنته به في الوقت الحالي

ios - كيفية تطبيق بروتوكول Hashable في سويفت لصفيف Int(بنية سلسلة مخصصة)

arrays string (3)

ما أريد القيام به

مشكلة

ما قرأت

سؤال

التحديثات

تحديث

الجواب القديم:

كيفية التنفيذ لبروتوكول Hashable

تطبيق بروتوكول Equatable

إرجاع hashValue محسوبة

الصورة الكبيرة

قراءة مفيدة أخرى

قروض

تحديث

إرجاع `hashValue` محسوبة