[ARROW-2653] [C++] Refactor hash table support

• Type: Task
• Status: Resolved
• Priority: Major
• Resolution: Fixed
• Affects Version/s: 0.11.1
• Fix Version/s: 0.12.0
• Component/s: C++
• Labels: pull-request-available
• External issue URL: https://github.com/apache/arrow/issues/15725
• Assignee: Antoine Pitrou
• Reporter: Antoine Pitrou
• Created: 31/May/18 14:28
• Updated: 11/Jan/23 07:22
• Resolved: 22/Nov/18 19:54

Description

Currently our hash table support is scattered in several places:

• compute/kernels/hash.cc
• util/hash.h and util/hash.cc
• builder.cc (in the DictionaryBuilder implementation)

Perhaps we should have something like a type-parametered hash table class (perhaps backed by non-owned memory) with several primitives:

• decide allocation size for a given number of items
• lookup an item
• insert an item
• decide whether resizing is needed
• resize to a new memory area
• ...

Issue Links

• supercedes: ARROW-1822 [C++] Add SSE4.2-accelerated hash kernels and use if host CPU supports
• supercedes: ARROW-2211 [C++] Use simpler hash functions for integers
• links to: GitHub Pull Request #3005