Hash join: Difference between revisions

{{task}}

 

 

 

 

=={{header|Bracmat}}==

This solution creates a hash table for the smaller relation in the function <code>join</code>. This function takes as arguments the smallest table, the biggest table and then three pieces of code: two patterns that describe each table's field order and code that generates one row of output. These pieces of code are inserted in a fixed skeleton of code using macro substitution.

(18.Alan)

(28.Glory)

)

&

Output:

<pre> (28.Alan.Ghosts)

=={{header|C sharp}}==

;using LINQ to Objects

using System.Collections.Generic;

using System.Linq;

}

}

 

{{out}}

Age: 28, Name: Alan, Nemesis: Ghosts

Age: 28, Name: Alan, Nemesis: Zombies

</pre>

 

=={{header|Common Lisp}}==

 

(defparameter *table-B* '(("Jonah" "Whales") ("Jonah" "Spiders") ("Alan" "Ghosts") ("Alan" "Zombies") ("Glory" "Buffy")))

(let ((val (car (gethash i *hash-table*))))

(loop for (a b) in val do

 

{{out}}

=={{header|D}}==

{{trans|Python}}

 

auto hashJoin(size_t index1, size_t index2, T1, T2)

// Hash phase.

h[s[index1]] ~= s;

// Join phase.

result ~= tuple(s, r);

return result;

}

T("Glory", "Buffy")];

 

writefln("(%s, %5s) (%5s, %7s)", row[0][], row[1][]);

{{out}}

<pre>(27, Jonah) (Jonah, Whales)

(28, Alan) ( Alan, Zombies)

(28, Glory) (Glory, Buffy)</pre>

 

=={{header|Erlang}}==

-module( hash_join ).

 

dict_find( error, _Key, _Value ) -> [];

dict_find( {ok, Values}, Key, Value ) -> [{X, {Key, Value}} || X <- Values].

{{out}}

<pre>

{{28,"Alan"},{"Alan","Zombies"}},

{{28,"Glory"},{"Glory","Buffy"}}]

</pre>

 

=={{header|Go}}==

 

import "fmt"

}

}

{{out}}

<pre>

{28 Alan} {Alan Zombies}

{28 Glory} {Glory Buffy}

</pre>

 

 

Placing all relations with the same selector value in a list in the hashtable allows us to join many to one/many relations.

import qualified Data.HashTable.ST.Basic as H

import Data.Hashable

readSTRef l

 

[(1, "Jonah"), (2, "Alan"), (3, "Glory"), (4, "Popeye")]

snd

("Alan", "Ghosts"), ("Alan", "Zombies"), ("Glory", "Buffy")]

fst

((3,"Glory"),("Glory","Buffy"))

((2,"Alan"),("Alan","Zombies"))

 

The task require hashtables; however, a cleaner and more functional solution would be to use Data.Map (based on binary trees):

import qualified Data.Map as M

import Data.List

where yMap = foldl' f M.empty ys

f m y = M.insertWith (++) (fy y) [y] m

 

[(1, "Jonah"), (2, "Alan"), (3, "Glory"), (4, "Popeye")]

snd

("Alan", "Ghosts"), ("Alan", "Zombies"), ("Glory", "Buffy")]

fst

((1,"Jonah"),("Jonah","Spiders"))

((1,"Jonah"),("Jonah","Whales"))

Data:

 

27 Jonah

18 Alan

Alan Zombies

Glory Buffy

 

The task does not specify the hash function to use, so we'll use an identity function. But [[SHA-1]] could be used instead, with a little more work (you'd need to convert the name into the bit vector needed by the SHA-1 interface). Practically speaking, though, the only benefit of SHA-1 in this context would be to slow down the join.

Implementation:

 

dojoin=:3 :0

c1=. {.{.y

)

 

 

Result:

 

┌─────┬──┬───────┐

│Jonah│27│Whales │

├─────┼──┼───────┤

│Glory│28│Buffy │

 

=={{header|OCaml}}==

This exploits the fact that Hashtbl implements a hash table that can store multiple values for a key, for an especially simple solution:

let h = Hashtbl.create 42 in

(* hash phase *)

(* join phase *)

List.concat (List.map (fun r ->

Sample run:

<pre>

 

=={{header|Perl}}==

 

sub hashJoin {

foreach my $row (hashJoin(\@table1, 1, \@table2, 0)) {

print Dumper($row), "\n";

{{out}}

<pre>

</pre>

 

{{out}}

 

=={{header|PHP}}==

function hashJoin($table1, $index1, $table2, $index2) {

// hash phase

foreach (hashJoin($table1, 1, $table2, 0) as $row)

print_r($row);

{{out}}

<pre>

 

)</pre>

 

=={{header|Python}}==

 

def hashJoin(table1, index1, table2, index2):

 

for row in hashJoin(table1, 1, table2, 0):

{{out}}

<pre>

 

=={{header|Racket}}==

(struct A (age name))

(struct B (name nemesis))

(key (in-value (B-name b)))

(age (in-list (hash-ref name->ages# key))))

 

{{out}}

#(struct:AB "Alan" 28 "Zombies")

#(struct:AB "Glory" 28 "Buffy"))</pre>

 

=={{header|REXX}}==

 

<pre>

age name nemesis

─── ──────────────────── ──────────────────────────────

</pre>

 

=={{header|Ruby}}==

# hash phase

h = table1.group_by {|s| s[index1]}

["Glory", "Buffy"]]

 

{{out}}

<pre>

[[28, "Glory"], ["Glory", "Buffy"]]

</pre>

 

=={{header|SQL}}==

 

 

 

{{out}}

 

=={{header|Tcl}}==

Tcl uses hash tables to implement both its associative arrays and its dictionaries.

# Only for lmap, which can be replaced with foreach

 

# Optimisation: if the first table is longer, do in reverse order

if {[llength $tableB] < [llength $tableA]} {

lreverse $pair

}]

 

foreach value $tableA {

}

#dict version# if {![dict exists $hashmap $key]} continue

}

}

 

foreach row $joined {

puts $row

{{out}}

<pre>

</pre>

 

Generic hash join. Arguments <code>left-key</code> and <code>right-key</code> are functions applied to the elements of the <code>left</code> and <code>right</code> sequences to retrieve the join key.

 

 

 

 

 

{{out}}

 

(((27 Jonah) (Jonah Whales)) ((27 Jonah) (Jonah Spiders)) ((18 Alan) (Alan Ghosts)) ((28 Alan) (Alan Ghosts)) ((18 Alan) (Alan Zombies)) ((28 Alan) (Alan Zombies)) ((28 Glory) (Glory Buffy)))</pre>

 

=={{header|zkl}}==

Join two tables by hashing on the common key (name). The resulting join is the intersection of the two tables.

nameNemesis:=T("Jonah","Whales", "Jonah","Spiders", "Alan","Ghosts",

"Alan","Zombies", "Glory","Buffy");

}

}

 

d.println(); // the union of the two tables

val:=d[name]; if (not val[1])return(Void.Skip);

String(name,":",d[name][1].concat(","));

zkl Dictionaries only have one key

<pre>

Jonah:Whales,Spiders

</pre>