Hash join: Difference between revisions

'''let''' ''C'' = the output table (starts out empty)

'''place''' ''b'' '''in''' multimap ''M_B'' under key ''b''(''j_B'')

'''let''' ''c'' = the concatenation of row ''a'' and row ''b''

'''place''' row ''c'' in table ''C''

{| style="border:none; border-collapse:collapse;"

|-

| style="border:none" |

 

 

| style="border:none; padding-left:1.5em;" rowspan="2" |

| style="border:none" |

 

 

|-

| style="border:none" | <code>Name</code> (i.e. column 1)

 

| style="border:none" | <code>Character</code> (i.e. column 0)

|}

 

<br><hr>

 

=={{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|Clojure}}==

(defn hash-join [table1 col1 table2 col2]

(let [hashed (group-by col1 table1)]

 

(pprint (sort-by :name (hash-join s :name r :name)))

 

{{out}}

 

=={{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)

foreach (const row; hashJoin!(1, 0)(table1, table2))

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

{{out}}

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

=={{header|Déjà Vu}}==

{{trans|Python}}

local :h {}

# hash phase

 

for row in hashJoin table1 1 table2 0:

{{out}}

<pre>[ [ 27 "Jonah" ] [ "Jonah" "Whales" ] ]

=={{header|EchoLisp}}==

Since this is a real, professional application, we build the hash tables in permanent (local) storage.

(define ages '((27 "Jonah") (18 "Alan") (28 "Glory") (18 "Popeye") (28 "Alan")))

(define nemesis '(("Jonah" "Whales") ("Jonah" "Spiders") ("Alan" "Ghosts") ("Alan" "Zombies") ("Glory" "Buffy")))

(n (local-get-value k 'NEMESIS)))

(writeln a n))

{{out}}

(28 "Alan") ("Alan" "Zombies")

(28 "Alan") ("Alan" "Ghosts")

(27 "Jonah") ("Jonah" "Spiders")

(27 "Jonah") ("Jonah" "Whales")

 

=={{header|ECL}}==

LeftRec := RECORD

UNSIGNED1 Age;

27 Jonah Spiders

*/

 

=={{header|Elixir}}==

{{trans|Ruby}}

def join(table1, index1, table2, index2) do

h = Enum.group_by(table1, fn s -> elem(s, index1) end)

{"Alan", "Zombies"},

{"Glory", "Buffy"}]

 

{{out}}

 

=={{header|Erlang}}==

-module( hash_join ).

 

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

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

{{out}}

<pre>

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

</pre>

 

=={{header|Forth}}==

Needs the FMS-SI (single inheritance) library code located here:

http://soton.mpeforth.com/flag/fms/index.html

include FMS-SI.f

include FMS-SILib.f

q free:

 

{{out}}

<pre>

 

=={{header|Go}}==

 

import "fmt"

}

}

{{out}}

<pre>

 

Semi-imperative style:

def hashJoin(table1, col1, table2, col2) {

 

q

}

 

More functional style:

def hashJoin(table1, col1, table2, col2) {

 

}.flatten()

}

 

Sample run (either version as the result is the same):

def s = [[age: 27, name: 'Jonah'],

[age: 18, name: 'Alan'],

 

hashJoin(s, "name", r, "name").sort {it.name}.each { println it }

 

produces:

 

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

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

fst

<pre>

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

 

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

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

fst

<pre>

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

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|Java}}==

{{trans|PHP}}

{{works with|Java|8}}

 

public class HashJoin {

return result;

}

 

<pre>[[27, Jonah], [Jonah, Whales]]

[[28, Alan], [Alan, Zombies]]

[[28, Glory], [Glory, Buffy]]</pre>

 

=={{header|jq}}==

 

===hashJoin===

# arrays, either of JSON objects, or of arrays.

 

reduce $hash[$key][] as $r (.; . + [ $row + $r ] )

else . end)

 

'''Example'''

[ {"age": 27, "name": "Jonah"},

{"age": 18, "name": "Alan"},

( hashJoin(table1; "name"; table2; "name"),

hashJoin(table1a; 1; table2a; 0)

{{out}}

 

{"age":27,"name":"Jonah","nemesis":"Whales"}

[28,"Alan","Alan","Ghosts"]

[28,"Alan","Alan","Zombies"]

 

===hashJoinArrays===

# index1 and index2 should be the 0-based indices of the join columns.

#

. + [ $r + $row[0:index2] + $row[index2+1:] ] )

else . end)

'''Example'''

 

In the following example, the previously defined pretty-print function (pp) and tables (table1 and table2)

are used, so their definitions are not repeated here.

{{out}}

 

[27,"Jonah","Whales"]

[28,"Alan","Ghosts"]

[28,"Alan","Zombies"]

 

=={{header|LFE}}==

(defun hash (column table)

(lists:foldl

(lc ((<- s (get-hash col-2 hashed)))

(merge r s)))))

 

Table definitions in the LFE REPL:

> (set ss '((#(age 27) #(name "Jonah"))

(#(age 18) #(name "Alan"))

(#(nemesis "Zombies") #(name "Alan"))

(#(nemesis "Buffy") #(name "Glory"))))

 

Output in LFE REPL:

> (hash-join ss 'name rs 'name)

(((#(age 27) #(name "Jonah") #(nemesis "Whales")))

(#(age 28) #(name "Alan") #(nemesis "Zombies")))

((#(age 28) #(name "Glory") #(nemesis "Buffy"))))

 

=={{header|Mathematica}} / {{header|Wolfram Language}}==

 

Updated version is now able to join wider tables by giving the index. The smaller table is hashed but this might result in different column ordering. Uses Associations introduced in Mathematica Version 10

t1=If[table1colindex != 1,table1[[All,Prepend[Delete[Range@Length@table1[[1]],table1colindex],table1colindex]]],table1];

t2=If[table2colindex != 1, table2[[All,Prepend[Delete[Range@Length@table2[[1]],table2colindex],table2colindex]]],table2];

Partition[Flatten[Map[f,{#[[2;;]],h[#[[1]]]}&/@t2

]],Length[t1[[1]]]+Length[t2[[1]]]-1]

Sample run:

<pre>

28 4 Glory 35 Buffy

</pre>

 

=={{header|Oberon-2}}==

Works with oo2c version 2

MODULE HashJoin;

IMPORT

DoJoinPhase(tableB,dict);

END HashJoin.

Output:

<pre>

=={{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}}==

S. = ; R. =

S.1 = 27 'Jonah' ; R.1 = "Jonah Whales"

if nems=='' then iterate /*No nemesis? Skip. */

say pad right(age,3) pad center(name,20) pad center(nems,30) /*display an "S". */

'''output''' &nbsp; when using the in-code relations (data):

<pre>

 

=={{header|Ring}}==

Table2 = [["Jonah", "Whales"], ["Jonah", "Spiders"], ["Alan", "Ghosts"], ["Alan", "Zombies"], ["Glory", "Buffy"]]

hTable = []

next

ok

{{out}}

<pre>

 

=={{header|Ruby}}==

# hash phase

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

["Glory", "Buffy"]]

 

 

{{out}}

 

=={{header|Run BASIC}}==

 

#mem execute("CREATE TABLE t_age(age,name)")

nemesis$ = #row nemesis$()

print age;" ";name$;" ";nemesis$

<pre>27 Jonah Spiders

27 Jonah Whales

 

=={{header|Rust}}==

 

// hash phase

}

// join phase

}

}

}

{{out}}

 

=={{header|Scala}}==

val hash = right.groupBy(_.head) withDefaultValue Seq()

left.flatMap(cols => hash(cols.last).map(cols ++ _.tail))

List("Glory", "Buffy"))

 

{{out}}

<pre>List(27, Jonah, Whales)

=={{header|Scheme}}==

{{works with|Gauche Scheme}}

 

(define ages '((27 Jonah) (18 Alan) (28 Glory) (18 Popeye) (28 Alan)))

(print (list (list age name)

person)))

{{output}}

<pre>

 

=={{header|Sidef}}==

var a = []

var h = Hash()

["Glory", "Buffy"]]

 

{{out}}

<pre>[[27, 'Jonah'], ['Jonah', 'Whales']]

 

=={{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

 

foreach row $joined {

puts $row

{{out}}

<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.

 

(18 Alan)

(28 Glory)

^(,l-entry ,r-entry)))))

 

 

{{out}}

 

=={{header|VBScript}}==

Dim t_age(4,1)

t_age(0,0) = 27 : t_age(0,1) = "Jonah"

Next

End Sub

 

{{Out}}

=={{header|Visual FoxPro}}==

Hashing using the common key (name) gives ambiguous results as the name column is not unique in either table (a unique key could be formed by using the age and name columns) . This implementation forces a unique key on the people table.

LOCAL i As Integer, n As Integer

CLOSE DATABASES ALL

RETURN a[1]

ENDFUNC

{{out}}

<pre>

18 Alan Zombies

28 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");

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

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

zkl Dictionaries only have one key

<pre>