ฉันเชื่อว่าคนส่วนใหญ่คุ้นเคยกับโครงสร้างข้อมูลตารางแฮชและในหลาย ๆ ที่ตารางแฮชถูกใช้เพื่อปรับปรุงประสิทธิภาพการค้นหา มีวิธีการในคลาสวัตถุของ Java:
hashcode int สาธารณะ ();
ตามการประกาศของวิธีนี้จะเห็นได้ว่าวิธีการส่งคืนค่าตัวเลขของประเภท int และเป็นวิธีการในท้องถิ่นดังนั้นจึงไม่มีการใช้งานเฉพาะในคลาสวัตถุ
ทำไมคลาสวัตถุจึงต้องการวิธีการดังกล่าว? ฟังก์ชั่นของมันคืออะไร? วันนี้เราจะหารือเกี่ยวกับวิธีการ HashCode โดยละเอียด
1. ฟังก์ชั่นของวิธี HashCode
สำหรับภาษาการเขียนโปรแกรมที่มีประเภทคอนเทนเนอร์ HashCode นั้นมีส่วนเกี่ยวข้องโดยทั่วไป เช่นเดียวกันในชวา ฟังก์ชั่นหลักของวิธี HashCode คือการทำงานตามปกติกับชุดที่ใช้แฮชชุดแฮชเช่น HashSet, HashMap และ Hashtable
ทำไมคุณถึงพูดอย่างนั้น? พิจารณาสถานการณ์ที่มีการแทรกวัตถุลงในคอลเลกชันวิธีการพิจารณาว่าวัตถุนั้นมีอยู่แล้วในคอลเลกชันแล้วหรือไม่? (หมายเหตุ: ไม่อนุญาตให้ใช้องค์ประกอบที่ซ้ำกันในคอลเลกชัน)
บางทีคนส่วนใหญ่อาจคิดว่าจะเรียกวิธีการเท่า ๆ กันเพื่อเปรียบเทียบทีละคนและวิธีนี้เป็นไปได้จริง อย่างไรก็ตามหากมีข้อมูลหนึ่งหมื่นชิ้นหรือข้อมูลเพิ่มเติมในชุดหากใช้วิธีเท่ากับเพื่อเปรียบเทียบทีละตัวประสิทธิภาพจะเป็นปัญหาอย่างหลีกเลี่ยงไม่ได้ ในเวลานี้ฟังก์ชั่นของวิธี HashCode จะสะท้อนให้เห็น เมื่อมีการเพิ่มวัตถุใหม่ลงในคอลเลกชันวิธีการ HashCode ของวัตถุจะเรียกว่าก่อนเพื่อให้ได้ค่า hashcode ที่สอดคล้องกัน ในความเป็นจริงในการใช้งาน HASHMAP เฉพาะตารางจะถูกใช้เพื่อบันทึกค่า hashcode ของวัตถุที่ได้รับการบันทึก หากไม่มีค่า HashCode ในตารางสามารถเก็บไว้ได้โดยตรงโดยไม่ต้องเปรียบเทียบใด ๆ หากค่า HashCode มีอยู่วิธีการเท่ากับของมันจะถูกเรียกให้เปรียบเทียบกับองค์ประกอบใหม่ หากสิ่งเดียวกันเป็นจริงที่อยู่อื่นจะไม่ถูกเก็บไว้ ดังนั้นจึงมีปัญหาในการแก้ไขข้อขัดแย้งที่นี่ ด้วยวิธีนี้จำนวนครั้งที่วิธีการเท่ากับจริง ๆ แล้วเรียกว่าลดลงอย่างมาก เพื่อให้ง่าย: วิธี HashCode ใน Java แมปข้อมูลที่เกี่ยวข้องกับวัตถุ (เช่นที่อยู่ที่เก็บข้อมูลของวัตถุเขตข้อมูลของวัตถุ ฯลฯ ) เป็นค่าตัวเลขตามกฎบางอย่างและค่านี้เรียกว่าค่าแฮช รหัสต่อไปนี้คือการใช้งานเฉพาะของวิธีการใน java.util.hashmap:
สาธารณะ V Put (k key, v value) {ถ้า (key == null) return putfornullkey (value); int hash = hash (key.hashcode ()); int i = indexfor (แฮช, table.length); สำหรับ (รายการ <k, v> e = ตาราง [i]; e! = null; e = e.next) {วัตถุ k; if (e.hash == hash && ((k = e.key) == key || key.equals (k))) {v oldValue = e.value; e.value = ค่า; E.RecordAccess (นี่); กลับ OldValue; }} ModCount ++; Addentry (แฮช, คีย์, ค่า, i); คืนค่า null; - วิธีการวางใช้เพื่อเพิ่มองค์ประกอบใหม่ให้กับ HashMap จากการใช้วิธีการเฉพาะเราสามารถทราบได้ว่าวิธีการ HashCode จะถูกเรียกก่อนเพื่อให้ได้ค่า HashCode ขององค์ประกอบจากนั้นตรวจสอบว่าค่า HashCode มีอยู่ในตารางหรือไม่ หากมีอยู่ให้โทรหาวิธี EQUALS เพื่อกำหนดใหม่ว่าองค์ประกอบมีอยู่หรือไม่ หากมีอยู่ให้อัปเดตค่าค่ามิฉะนั้นเพิ่มองค์ประกอบใหม่ลงใน HashMap จากที่นี่เราจะเห็นได้ว่ามีวิธีการ HashCode เพื่อลดจำนวนการโทรไปยังวิธีการเท่ากับและปรับปรุงประสิทธิภาพของโปรแกรม
เพื่อนบางคนคิดผิดพลาดว่าโดยค่าเริ่มต้น HashCode จะส่งคืนที่อยู่ที่เก็บข้อมูลของวัตถุ ในความเป็นจริงมุมมองนี้ไม่สมบูรณ์ มันเป็นความจริงที่ JVM บางตัวส่งคืนที่อยู่ที่เก็บข้อมูลของวัตถุโดยตรงเมื่อนำไปใช้ แต่นี่ไม่ใช่กรณีส่วนใหญ่ของเวลา อาจกล่าวได้ว่าที่อยู่จัดเก็บอาจเกี่ยวข้องกับมัน ต่อไปนี้คือการนำค่าแฮชแฮชสร้างมาใช้ในฮอตสปอต JVM:
intlan inline intptr_t get_next_hash (เธรด * ตัวเอง, oop obj) {ค่า intptr_t = 0; ถ้า (hashCode == 0) {// แบบฟอร์มนี้ใช้ RNG ที่ไม่ได้รับการดูแลทั่วโลก RNG // ดังนั้นจึงเป็นไปได้ที่สองเธรดในการแข่งขันและสร้าง RNG เดียวกัน // ในระบบ MP เราจะมีการเข้าถึง RW จำนวนมากในระดับโลกดังนั้นกลไก // จะทำให้เกิดการเข้าชมที่เชื่อมโยงกันมากมาย ค่า = OS :: RANDOM (); } อื่นถ้า (hashCode == 1) {// รูปแบบนี้มีคุณสมบัติของความเสถียร (idempotent) // ระหว่างการดำเนินการ STW สิ่งนี้มีประโยชน์ในแผนการซิงโครไนซ์ 1-0 // intptr_t addrbits = intptr_t (obj) >> 3; value = addrbits ^ (addrbits >> 5) ^ gvars.stwrandom; } อื่นถ้า (hashCode == 2) {value = 1; // สำหรับการทดสอบความไว} อื่นถ้า (hashCode == 3) {value = ++ gvars.hcequence; } อื่นถ้า (hashCode == 4) {value = intptr_t (obj); } else {// รูปแบบ XOR-shift ของ Marsaglia ที่มีสถานะเฉพาะเธรด // นี่อาจเป็นการใช้งานโดยรวมที่ดีที่สุด-เราจะ // น่าจะทำให้สิ่งนี้เป็นค่าเริ่มต้นในการเผยแพร่ในอนาคต t = self ที่ไม่ได้ลงชื่อ-> _ hashstatex; t ^= (t << 11); self-> _ hashstatex = self-> _ hashstatey; self-> _ hashstatey = self-> _ hashstatez; self-> _ hashstatez = self-> _ hashstatew; v = self-> _ hashstatew; v = (v ^ (v >> 19)) ^ (t ^ (t >> 8)); ตัวเอง-> _ hashstatew = v; ค่า = V; } value & = markoopdesc :: hash_mask; if (value == 0) value = 0xBad; ยืนยัน (ค่า! = markoopdesc :: no_hash, "ค่าคงที่"); TEVENT (HashCode: สร้าง); ค่าส่งคืน;}การใช้งานนี้อยู่ในฮอตสปอต/src/share/vm/runtime/synchronizer.cpp ไฟล์
ดังนั้นบางคนอาจบอกว่าเราสามารถตัดสินได้โดยตรงว่าวัตถุสองชิ้นนั้นเท่าเทียมกันตามค่าแฮชโฟตอนหรือไม่? มันเป็นไปไม่ได้อย่างแน่นอนเพราะวัตถุที่แตกต่างกันอาจสร้างค่าแฮชโค้ดเดียวกัน แม้ว่าจะเป็นไปไม่ได้ที่จะตัดสินว่าวัตถุสองชิ้นมีค่าเท่ากันตามค่า HashCode หรือไม่คุณสามารถตัดสินได้โดยตรงว่าวัตถุทั้งสองนั้นไม่เท่ากันตามค่า HashCode หากค่า HashCode ของวัตถุทั้งสองไม่เท่ากันพวกเขาจะต้องเป็นสองวัตถุที่แตกต่างกัน หากคุณต้องการตรวจสอบว่าวัตถุสองชิ้นมีค่าเท่ากันอย่างแท้จริงคุณต้องใช้วิธี Equals
กล่าวคือสำหรับสองวัตถุหากผลลัพธ์ที่ได้จากการเรียกวิธี EQUALS เป็นจริงค่า HashCode ของวัตถุทั้งสองจะต้องเท่ากัน
หากผลลัพธ์ที่ได้จากวิธี Equals เป็นเท็จค่า HashCode ของวัตถุทั้งสองอาจไม่แตกต่างกัน
หากค่า HashCode ของวัตถุทั้งสองไม่เท่ากันผลลัพธ์ที่ได้จากวิธี Equals จะต้องเป็นเท็จ
หากค่า HashCode ของวัตถุทั้งสองเท่ากันผลลัพธ์ที่ได้จากวิธีการเท่ากับจะไม่ทราบ
2. วิธี Equals และวิธีการ HashCode
ในบางกรณีเมื่อออกแบบคลาสโปรแกรมเมอร์จำเป็นต้องเขียนวิธี Equals ใหม่เช่นคลาสสตริง แต่อย่าลืมทราบว่าในขณะที่เขียนวิธี Equals ใหม่พวกเขาจะต้องเขียนวิธี HashCode ใหม่ ทำไมคุณถึงพูดอย่างนั้น?
มาดูตัวอย่างด้านล่าง:
แพ็คเกจ com.cxh.test1; นำเข้า java.util.hashmap; นำเข้า java.util.hashset; นำเข้า java.util.set; คนชั้นเรียน {ชื่อสตริงส่วนตัว; อายุ int ส่วนตัว; คนสาธารณะ (ชื่อสตริงอายุ int) {this.name = ชื่อ; this.age = อายุ; } การตั้งค่าโมฆะสาธารณะ (อายุ int) {this.age = อายุ; } @Override บูลีนสาธารณะเท่ากับ (Object obj) {// วิธีการที่สร้างขึ้นอัตโนมัติ todo stub return this.name.equals (((คน) obj .name) && this.age == ((คน) obj) .age; }} คลาสสาธารณะหลัก {โมฆะคงที่สาธารณะหลัก (สตริง [] args) {คน p1 = คนใหม่ ("แจ็ค", 12); System.out.println (P1.HashCode ()); hashmap <คนจำนวนเต็ม> hashmap = new hashmap <คนจำนวนเต็ม> (); hashmap.put (p1, 1); System.out.println (hashmap.get (คนใหม่ ("แจ็ค", 12));}}ที่นี่ฉันมีเพียงการเขียนวิธี Equals ใหม่ซึ่งหมายความว่าหากคนสองคนมีชื่อและอายุเท่ากันพวกเขาจะถือว่าเป็นคนเดียวกัน
ความตั้งใจดั้งเดิมของรหัสนี้คือการส่งออกผลลัพธ์ของ "1" แต่ในความเป็นจริงมันส่งออก "null" ทำไม เหตุผลก็คือคุณลืมที่จะเขียนวิธี HashCode ใหม่ในขณะที่เขียนวิธี Equals ใหม่
แม้ว่าวัตถุสองชิ้นที่มีชื่อและอายุเดียวกันจะถูกกำหนดอย่างสมเหตุสมผลให้เท่ากัน (คล้ายกับคลาสสตริง) แต่ก็ควรทราบว่าโดยค่าเริ่มต้นวิธีการ HashCode แมปที่อยู่ที่เก็บข้อมูลของวัตถุ จากนั้นก็ไม่น่าแปลกใจที่ผลลัพธ์ผลลัพธ์ของรหัสข้างต้นคือ "null" เหตุผลนั้นง่ายมากวัตถุที่ชี้ไปที่ P1 และ
System.out.println (hashmap.get (คนใหม่ ("แจ็ค", 12)); คนใหม่ ("แจ็ค", 12) ในประโยคนี้สร้างวัตถุสองวัตถุและที่อยู่จัดเก็บของพวกเขาจะต้องแตกต่างกัน
สาธารณะ v รับ (คีย์วัตถุ) {ถ้า (key == null) return getForNullKey (); int hash = hash (key.hashcode ()); สำหรับ (รายการ <k, v> e = ตาราง [indexfor (แฮช, table.length)]; e! = null; e = e.next) {object k; if (e.hash == hash && ((k = e.key) == key || key.equals (k))) ส่งคืน e.value; } return null; -ดังนั้นเมื่อ HashMap ถูกใช้เพื่อรับเนื่องจากค่า hashcdoe ที่ได้รับนั้นแตกต่างกัน (โปรดทราบว่ารหัสข้างต้นอาจได้รับค่าแฮชโฟตอนเดียวกันในบางกรณี แต่ความน่าจะเป็นค่อนข้างเล็กเพราะแม้ว่าที่อยู่การจัดเก็บของวัตถุทั้งสองจะแตกต่างกัน
ดังนั้นหากคุณต้องการให้รหัสด้านบนส่งออกผลลัพธ์ "1" มันง่ายมาก คุณเพียงแค่ต้องเขียนวิธี HashCode ใหม่และทำให้วิธีการเท่ากับและวิธี HashCode มักจะสอดคล้องกันอย่างมีเหตุผล
แพ็คเกจ com.cxh.test1; นำเข้า java.util.hashmap; นำเข้า java.util.hashset; นำเข้า java.util.set; คนชั้นเรียน {ชื่อสตริงส่วนตัว; อายุ int ส่วนตัว; คนสาธารณะ (ชื่อสตริงอายุ int) {this.name = ชื่อ; this.age = อายุ; } การตั้งค่าโมฆะสาธารณะ (อายุ int) {this.age = อายุ; } @Override public int hashCode () {// todo วิธีการที่สร้างขึ้นอัตโนมัติ stub return name.hashCode ()*37+อายุ; } @Override บูลีนสาธารณะเท่ากับ (Object obj) {// วิธีการที่สร้างขึ้นอัตโนมัติ todo stub return this.name.equals (((คน) obj .name) && this.age == ((คน) obj) .age; }} คลาสสาธารณะหลัก {โมฆะคงที่สาธารณะหลัก (สตริง [] args) {คน p1 = คนใหม่ ("แจ็ค", 12); System.out.println (P1.HashCode ()); hashmap <คนจำนวนเต็ม> hashmap = new hashmap <คนจำนวนเต็ม> (); hashmap.put (p1, 1); System.out.println (hashmap.get (คนใหม่ ("แจ็ค", 12))); -ด้วยวิธีนี้ผลลัพธ์ผลลัพธ์จะเป็น "1"
ข้อความต่อไปนี้ถูกตัดตอนมาจากหนังสือ Java ที่มีประสิทธิภาพ:
ในระหว่างการดำเนินการโปรแกรมตราบใดที่ข้อมูลที่ใช้ในการดำเนินการเปรียบเทียบของวิธี Equals ยังไม่ได้รับการแก้ไขวิธีการ HashCode จะต้องส่งคืนจำนวนเต็มเดียวกันอย่างต่อเนื่อง
หากวัตถุทั้งสองมีค่าเท่ากันตามวิธีการเท่ากับการเรียกใช้วิธีแฮชโฟตอนของวัตถุทั้งสองจะต้องส่งคืนผลลัพธ์จำนวนเต็มเดียวกัน
หากวัตถุทั้งสองถูกเปรียบเทียบความไม่เท่าเทียมกันตามวิธีการเท่ากับวิธี HashCode ไม่จำเป็นต้องส่งคืนจำนวนเต็มที่แตกต่างกัน
เป็นเรื่องง่ายที่จะเข้าใจบทความที่สองและสาม แต่บทความแรกมักถูกละเว้น นอกจากนี้ยังมีข้อความที่คล้ายกับอันแรกในหน้า P495 ในหนังสือ "Java Programming Thought"::
"ปัจจัยที่สำคัญที่สุดในการออกแบบ hashCode () คือ: เมื่อใดก็ตามที่คุณเรียก HashCode () บนวัตถุเดียวกันค่าเดียวกันควรถูกสร้างขึ้นหากวัตถุถูกเพิ่มลงใน HashMap ด้วย put () และค่า hashcode อื่นจะถูกสร้างขึ้นเมื่อใช้ข้อมูลที่ใช้งานได้ วิธี HashCode () จะสร้างรหัสแฮชที่แตกต่างกัน "
นี่คือตัวอย่าง:
แพ็คเกจ com.cxh.test1; นำเข้า java.util.hashmap; นำเข้า java.util.hashset; นำเข้า java.util.set; คนชั้นเรียน {ชื่อสตริงส่วนตัว; อายุ int ส่วนตัว; คนสาธารณะ (ชื่อสตริงอายุ int) {this.name = ชื่อ; this.age = อายุ; } การตั้งค่าโมฆะสาธารณะ (อายุ int) {this.age = อายุ; } @Override public int hashCode () {// todo วิธีการที่สร้างขึ้นอัตโนมัติ stub return name.hashCode ()*37+อายุ; } @Override บูลีนสาธารณะเท่ากับ (Object obj) {// วิธีการที่สร้างขึ้นอัตโนมัติ todo stub return this.name.equals (((คน) obj .name) && this.age == ((คน) obj) .age; }} คลาสสาธารณะหลัก {โมฆะคงที่สาธารณะหลัก (สตริง [] args) {คน p1 = คนใหม่ ("แจ็ค", 12); System.out.println (P1.HashCode ()); hashmap <คนจำนวนเต็ม> hashmap = new hashmap <คนจำนวนเต็ม> (); hashmap.put (p1, 1); P1.Setage (13); System.out.println (hashmap.get (p1)); -ผลลัพธ์ของเอาต์พุตรหัสนี้คือ "null" และทุกคนจะต้องชัดเจนเกี่ยวกับเหตุผล
ดังนั้นเมื่อออกแบบวิธีการ HashCode และวิธีการเท่ากับวิธีหากข้อมูลในวัตถุมีความผันผวนจะเป็นการดีที่สุดที่จะไม่พึ่งพาฟิลด์นี้ในวิธีการเท่ากับและวิธีการ HashCode
ข้างต้นเป็นเนื้อหาทั้งหมดของบทความนี้ ฉันหวังว่ามันจะเป็นประโยชน์ต่อการเรียนรู้ของทุกคนและฉันหวังว่าทุกคนจะสนับสนุน wulin.com มากขึ้น