Looking for breakthrough ideas for innovation challenges? Try Patsnap Eureka!

Method and device for processing table items based on Hash table

A processing method and a technology of a processing device, which are applied in the field of communication, can solve problems such as the contradiction between performance and capacity, low utilization rate of hash table space, and few entries

Active Publication Date: 2012-09-19
ZTE CORP
View PDF3 Cites 39 Cited by
  • Summary
  • Abstract
  • Description
  • Claims
  • Application Information

AI Technical Summary

Problems solved by technology

[0003] In the current hash storage and query methods, the ubiquitous problem is the contradiction between performance and capacity
During the hash operation, although the key values ​​of each entry are different, the calculation results obtained by the hash function may be the same, which will cause conflicts in the storage space
On the one hand, in order to minimize conflicts and ensure query performance, that is, one-time hit rate, the traditional hash table structure adopts a hash method when storing entries, that is, the storage addresses obtained through the hash function are often not continuous, so the hash table structure The space utilization rate of the Greek table is not high, and it will cause a very large waste of storage space when storing the table items. There are not many table items that can be stored, and the capacity index cannot meet the requirements.
On the other hand, in order to improve the lookup speed, the traditional hash table structure mostly uses the result of a hash calculation to index into the hash index table for lookup, but this will greatly increase the probability of collisions

Method used

the structure of the environmentally friendly knitted fabric provided by the present invention; figure 2 Flow chart of the yarn wrapping machine for environmentally friendly knitted fabrics and storage devices; image 3 Is the parameter map of the yarn covering machine
View more

Image

Smart Image Click on the blue labels to locate them in the text.
Viewing Examples
Smart Image
  • Method and device for processing table items based on Hash table
  • Method and device for processing table items based on Hash table
  • Method and device for processing table items based on Hash table

Examples

Experimental program
Comparison scheme
Effect test

Embodiment Construction

[0086] It should be understood that the specific embodiments described here are only used to explain the present invention, not to limit the present invention.

[0087] Such as figure 1 as shown, figure 1 It is a flow chart of steps for storing entries in the hash table-based entry processing method of the first embodiment of the present invention. The hash table-based entry processing method mentioned in this embodiment includes:

[0088] Step S101, when the entries are stored, the entries to be stored are arranged in order and stored in the result table;

[0089] Step S102, using the double hash function of the index table to calculate the hash value of the key value of the entry to be stored;

[0090] Step S103, storing the hash value and the address pointer of the result table where the entry to be stored is located in a free position in the index table.

[0091] In this embodiment, the index table and the result table are separated, the structure of the index table is ...

the structure of the environmentally friendly knitted fabric provided by the present invention; figure 2 Flow chart of the yarn wrapping machine for environmentally friendly knitted fabrics and storage devices; image 3 Is the parameter map of the yarn covering machine
Login to View More

PUM

No PUM Login to View More

Abstract

The invention discloses a method and a device for processing table items based on a Hash table. The method comprises the steps of: during table item storage, storing table items to be stored in a result table in a sequential arrangement manner; calculating Hash values of key values of the table items to be stored by using dual Hash functions of an index table; and storing the Hash values and address pointers of the result table of the table items to be stored at idle positions in the index table. According to the invention, while lower access frequency and higher inquiry speed are guaranteed, the clause memory capacity of the service table items is increased effectively, the capacity of the Hash table for supporting possible services is increased, high spatial utilization rate is achieved for the Hash table, in addition, the probability of conflicts is reduced, and thus, the performance and the capacity of the Hash table are balanced.

Description

technical field [0001] The invention relates to the field of communication technology, in particular to a hash table-based entry processing method and device thereof. Background technique [0002] In the field of communication technology, a hash algorithm is often used for exact matching query of service table items. The hash function is used to perform hash operation on the key value of the business table entry, and the obtained calculation result value corresponds to the storage space in the hash table, that is, the hash operation result is addressed to realize the storage and operation of the table item. Inquire. [0003] In the current hash storage and query methods, the ubiquitous problem is the contradiction between performance and capacity. During the hash operation, although the key values ​​of each table entry are different, the operation results obtained through the hash function calculation may be the same, which will cause conflicts in the storage space. On th...

Claims

the structure of the environmentally friendly knitted fabric provided by the present invention; figure 2 Flow chart of the yarn wrapping machine for environmentally friendly knitted fabrics and storage devices; image 3 Is the parameter map of the yarn covering machine
Login to View More

Application Information

Patent Timeline
no application Login to View More
Patent Type & Authority Applications(China)
IPC IPC(8): G06F17/30
Inventor 孙远航张炜史顺达陈伟
Owner ZTE CORP
Who we serve
  • R&D Engineer
  • R&D Manager
  • IP Professional
Why Patsnap Eureka
  • Industry Leading Data Capabilities
  • Powerful AI technology
  • Patent DNA Extraction
Social media
Patsnap Eureka Blog
Learn More
PatSnap group products