WO2019171129A1 - Collision-free hash map - Google Patents
Collision-free hash map Download PDFInfo
- Publication number
- WO2019171129A1 WO2019171129A1 PCT/IB2018/051435 IB2018051435W WO2019171129A1 WO 2019171129 A1 WO2019171129 A1 WO 2019171129A1 IB 2018051435 W IB2018051435 W IB 2018051435W WO 2019171129 A1 WO2019171129 A1 WO 2019171129A1
- Authority
- WO
- WIPO (PCT)
- Prior art keywords
- label
- input
- value
- hash map
- hash
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Ceased
Links
Classifications
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F12/00—Accessing, addressing or allocating within memory systems or architectures
- G06F12/02—Addressing or allocation; Relocation
- G06F12/08—Addressing or allocation; Relocation in hierarchically structured memory systems, e.g. virtual memory systems
- G06F12/10—Address translation
- G06F12/1009—Address translation using page tables, e.g. page table structures
- G06F12/1018—Address translation using page tables, e.g. page table structures involving hashing techniques, e.g. inverted page tables
Definitions
- Input-Label hash map contains Input as the key and the corresponding unique label removed from the queue by the hash function for the Input as the value.
- Label- Value hash map contains the unique label as the key and the value as the Value Object corresponding to the Input for which the hash function generated the unique label (by removing an unique label atomically from a queue of unique labels for the Input) or the key.
- Any insert operation in the Collision-Free Hash Map results in lookup of the Input-Label hash map to check if it contains an entry with key as Input. Then since the entry would not be present for an insert operation we first create an entry in the Input-Label hash map consisting of Input as the key and the corresponding unique label removed by the hash function for the Input as the value.
Landscapes
- Engineering & Computer Science (AREA)
- Theoretical Computer Science (AREA)
- Physics & Mathematics (AREA)
- General Engineering & Computer Science (AREA)
- General Physics & Mathematics (AREA)
- Information Retrieval, Db Structures And Fs Structures Therefor (AREA)
Abstract
Here we provide hash map functionality such that for each corresponding Input there will be one and only corresponding Value Object which could be a group contiguous memory blocks holding some data or just a pointer to a memory location, etc. We achieve the above by using a special hash function which removes atomically an unique label from a queue of unique labels and maintains two hash maps namely Input-Label hash map and Label-Value hash map. Input-Label hash map contains Input as the key and the corresponding unique label removed from the queue by the hash function for the Input as the value. Similarly Label-Value hash map contains the unique label as the key and the value as the Value Object corresponding to the Input for which the hash function generated the unique label or the key.
Description
Collision-Free Hash Map
In this invention we provide hash map functionality with no collisions for any entry in the hash map. In other words for each corresponding Input (or sometimes referred as key) there will be one and only corresponding Value Object which could be a group contiguous memory blocks holding some data or just a pointer to a memory location, etc. We achieve the above by using a special hash function which removes atomically an unique label from a queue (queue elements may be linked using a doubly linked list) of unique labels and maintains two hash maps namely Input-Label hash map and Label- Value hash map. Input-Label hash map contains Input as the key and the corresponding unique label removed from the queue by the hash function for the Input as the value. Similarly Label- Value hash map contains the unique label as the key and the value as the Value Object corresponding to the Input for which the hash function generated the unique label (by removing an unique label atomically from a queue of unique labels for the Input) or the key. Any insert operation in the Collision-Free Hash Map results in lookup of the Input-Label hash map to check if it contains an entry with key as Input. Then since the entry would not be present for an insert operation we first create an entry in the Input-Label hash map consisting of Input as the key and the corresponding unique label removed by the hash function for the Input as the value. Similarly we create a corresponding entry in the Label- Value hash map with the unique label removed from the queue by the hash function for the Input as the key and the Value Object corresponding to the Input as the value as explained above. Delete operation in the Collision-Free Hash Map results in first deleting the entry corresponding to the Input in the Input-Label hash map but before this operation the unique label corresponding to the Input is stored in a temporary variable. Finally we delete the entry corresponding to the unique label stored in the temporary variable from the Label- Value hash map. For search or lookups in the Collision-Free Hash map we first do a lookup in the Input-Label hash map to get the unique label as value for the corresponding Input as key. The finally we do a lookup in the Label-Value hash map with the unique label we got previously as the key and we retrieve the Value object from the Label- Value hash map.
Claims
1. In this invention we provide hash map functionality with no collisions for any entry in the hash map. In other words for each corresponding Input (or sometimes referred as key) there will be one and only corresponding Value Object which could be a group contiguous memory blocks holding some data or just a pointer to a memory location, etc. We achieve the above by using a special hash function which removes atomically an unique label from a queue (queue elements may be linked using a doubly linked list) of unique labels and maintains two hash maps namely Input-Label hash map and Label- Value hash map. Input-Label hash map contains Input as the key and the corresponding unique label removed from the queue by the hash function for the Input as the value. Similarly Label- Value hash map contains the unique label as the key and the value as the Value Object corresponding to the Input for which the hash function generated the unique label (by removing an unique label atomically from a queue of unique labels for the Input) or the key. Any insert operation in the Collision-Free Hash Map results in lookup of the Input-Label hash map to check if it contains an entry with key as Input. Then since the entry would not be present for an insert operation we first create an entry in the Input-Label hash map consisting of Input as the key and the corresponding unique label removed by the hash function for the Input as the value. Similarly we create a corresponding entry in the Label- Value hash map with the unique label removed from the queue by the hash function for the Input as the key and the Value Object corresponding to the Input as the value as explained above. Delete operation in the Collision-Free Hash Map results in first deleting the entry corresponding to the Input in the Input-Label hash map but before this operation the unique label corresponding to the Input is stored in a temporary variable. Finally we delete the entry corresponding to the unique label stored in the temporary variable from the Label- Value hash map. For search or lookups in the Collision-Free Hash map we first do a lookup in the Input-Label hash map to get the unique label as value for the corresponding Input as key. The finally we do a lookup in the Label- Value hash map with the unique label we got previously as the key and we retrieve the Value object from the Label- Value hash map. The above novel technique of providing a Collision-Free Hash Map is the claim for this invention.
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| PCT/IB2018/051435 WO2019171129A1 (en) | 2018-03-06 | 2018-03-06 | Collision-free hash map |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| PCT/IB2018/051435 WO2019171129A1 (en) | 2018-03-06 | 2018-03-06 | Collision-free hash map |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| WO2019171129A1 true WO2019171129A1 (en) | 2019-09-12 |
Family
ID=67845912
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| PCT/IB2018/051435 Ceased WO2019171129A1 (en) | 2018-03-06 | 2018-03-06 | Collision-free hash map |
Country Status (1)
| Country | Link |
|---|---|
| WO (1) | WO2019171129A1 (en) |
Cited By (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US11636224B2 (en) | 2019-12-19 | 2023-04-25 | Micro Focus Llc | Generating hash values for input strings |
| CN117171162A (en) * | 2023-08-03 | 2023-12-05 | 湖南天河国云科技有限公司 | Hidden query method, device and storage medium based on collision-free hash mapping |
Citations (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US7058639B1 (en) * | 2002-04-08 | 2006-06-06 | Oracle International Corporation | Use of dynamic multi-level hash table for managing hierarchically structured information |
| US20080229056A1 (en) * | 2007-03-12 | 2008-09-18 | Broadcom Corporation | Method and apparatus for dual-hashing tables |
-
2018
- 2018-03-06 WO PCT/IB2018/051435 patent/WO2019171129A1/en not_active Ceased
Patent Citations (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US7058639B1 (en) * | 2002-04-08 | 2006-06-06 | Oracle International Corporation | Use of dynamic multi-level hash table for managing hierarchically structured information |
| US20080229056A1 (en) * | 2007-03-12 | 2008-09-18 | Broadcom Corporation | Method and apparatus for dual-hashing tables |
Cited By (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US11636224B2 (en) | 2019-12-19 | 2023-04-25 | Micro Focus Llc | Generating hash values for input strings |
| US12147569B2 (en) | 2019-12-19 | 2024-11-19 | Micro Focus Llc | Generating hash values for input strings |
| CN117171162A (en) * | 2023-08-03 | 2023-12-05 | 湖南天河国云科技有限公司 | Hidden query method, device and storage medium based on collision-free hash mapping |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| WO2015066489A3 (en) | Efficient implementations for mapreduce systems | |
| EP3035613B1 (en) | Ccn routing using hardware-assisted hash tables | |
| WO2019179538A3 (en) | Shared blockchain data storage | |
| US20180300207A1 (en) | Method and device for file backup and recovery | |
| EP4407500A3 (en) | System and method of controllably disclosing sensitive data | |
| WO2019072266A3 (en) | Traversing smart contract database through logic map | |
| WO2017023385A3 (en) | Secure searchable and shareable remote storage system and method | |
| EP4415327A3 (en) | Methods and systems for a consistent distributed memory pool in a blockchain network | |
| CN107454161A (en) | A data backup method and device | |
| US9465954B1 (en) | Method and system for tracking masking of data | |
| CN109032803B (en) | Data processing method and device and client | |
| CN104268015A (en) | Implementation method of high-availability timer of embedded equipment and timer | |
| US20160366534A1 (en) | Method of and server for communicating with a remote device in a machine to machine wireless communication network | |
| MY208854A (en) | Access node selection in 5g network for non-3gpp and non-cellular access, also indicating regional requirement according to lawful interception | |
| WO2019171129A1 (en) | Collision-free hash map | |
| US8493249B2 (en) | Compression match enumeration | |
| Grechnikov | Collisions for 72-step and 73-step SHA-1: Improvements in the Method of Characteristics | |
| CN105426417B (en) | A kind of method of geographical location information in quick lookup smart phone | |
| CN107547378B (en) | VPN route learning method and device | |
| NZ735617A (en) | Aggregating high volumes of temporal data from multiple overlapping sources | |
| CN111176830B (en) | Information flow distribution method, device and server system | |
| CN106990938B (en) | Random number acquisition method and device and electronic equipment | |
| WO2019211644A2 (en) | Event publisher module for in-memory hash map | |
| US11343071B2 (en) | Extended ciphertexts | |
| JP6344348B2 (en) | Buffer control device, communication node, and relay device |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| NENP | Non-entry into the national phase |
Ref country code: DE |
|
| 122 | Ep: pct application non-entry in european phase |
Ref document number: 18909096 Country of ref document: EP Kind code of ref document: A1 |