Utilization and Power Efficient Hashing
First Claim
1. A method, comprising:
- inserting a key in a selected bucket in accordance with a bucket identifier generated by a hash function, wherein the selected bucket is one of a plurality of buckets of a hash table configured in at least one memory;
determining respective unique bit strings based upon corresponding bit positions for a plurality of keys in the selected bucket, the plurality of keys including the inserted key; and
inserting the respective unique bit strings in a table location corresponding to the bucket identifier, wherein the table location is one of a plurality of table locations in at least one control table configured in the at least one memory.
4 Assignments
0 Petitions
Accused Products
Abstract
Methods, systems, and computer readable storage medium embodiments for hashing with improved utilization and power efficiency are disclosed. Some embodiments include inserting a key in a selected bucket in accordance with an bucket identifier generated by a hash function, wherein the selected bucket is one of a plurality of buckets of a hash table configured in at least one memory, determining respective unique bit strings based upon corresponding bit positions for a plurality of keys in the selected bucket including the inserted key, inserting the respective unique bit strings in a table location corresponding to the bucket identifier, wherein the table location is one of a plurality of table locations in at least one control table configured in the at least one memory. Other embodiments include lookup operations in a hash table.
35 Citations
20 Claims
-
1. A method, comprising:
-
inserting a key in a selected bucket in accordance with a bucket identifier generated by a hash function, wherein the selected bucket is one of a plurality of buckets of a hash table configured in at least one memory; determining respective unique bit strings based upon corresponding bit positions for a plurality of keys in the selected bucket, the plurality of keys including the inserted key; and inserting the respective unique bit strings in a table location corresponding to the bucket identifier, wherein the table location is one of a plurality of table locations in at least one control table configured in the at least one memory. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10)
-
-
11. A method, comprising:
-
determining a bucket identifier generated by a hash function for a key; accessing a control table in a memory using the bucket identifier; determining a bit string from the key, wherein the bit string is formed based upon a subset of bit positions of the key; determining a bucket entry identifier based upon the bit string and the bucket identifier, wherein the bucket identifier corresponds to a selected bucket in a hash table; and accessing a selected bucket entry in the selected bucket using the bucket entry identifier. - View Dependent Claims (12, 13, 14)
-
-
15. A system, comprising:
-
a hash table configured in at least one memory; a control table configured in the at least one memory; and a hash table controller configured to; insert a key in a selected bucket in accordance with a bucket identifier generated by a hash function, wherein the selected bucket is one of a plurality of buckets of a hash table configured in at least one memory; determine respective unique bit strings based upon corresponding bit positions for a plurality of keys in the selected bucket, the plurality of keys including the inserted key; and insert the respective unique bit strings in a table location corresponding to the bucket identifier, wherein the table location is one of a plurality of table locations in at least one control table configured in the at least one memory. - View Dependent Claims (16, 17, 18)
-
-
19. A non-transitory computer readable storage medium storing instructions that, when executed by a processor, performs a method comprising:
-
inserting a key in a selected bucket in accordance with a bucket identifier generated by a hash function, wherein the selected bucket is one of a plurality of buckets of a hash table configured in at least one memory; determining respective unique bit strings based upon corresponding bit positions for a plurality of keys in the selected bucket, the plurality of keys including the inserted key; and inserting the respective unique bit strings in a table location corresponding to the bucket identifier, wherein the table location is one of a plurality of table locations in at least one control table configured in the at least one memory. - View Dependent Claims (20)
-
Specification