Hash join: Difference between revisions

{{trans|Python}}

DefaultDict[String, [(Int, String)]] h

L(s) table1

L(row) hash_join(table1, table2)

{{out}}

The vertical bars distinguish AppleScript reserved words ('''name''' and '''character''' here) from field name literal strings.

-- HASH JOIN -----------------------------------------------------------------

set my text item delimiters to dlm

return lstParts

{{Out}}

<pre>{{age:27, |name|:"Jonah", |character|:"Jonah", nemesis:"Whales"},

=={{header|AWK}}==

# syntax: GAWK -f HASH_JOIN.AWK [-v debug={0|1}] TABLE_A TABLE_B

#

return(tmp)

}

<p>TABLE_A input:</p>

<pre>

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

=={{header|C++}}==

#include <string>

#include <vector>

}

{{out}}

<pre>Table A:

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

=={{header|F_Sharp|F#}}==

let main argv =

let table1 = [27, "Jonah";

|> Seq.toList

|> printfn "%A"

{{out}}

<pre>[((27, "Jonah"), ("Jonah", "Whales")); ((27, "Jonah"), ("Jonah", "Spiders"));

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

===ES6===

'use strict';

})();

{{Out}}

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

{{works with|Julia|0.6}}

For dataframes there is a builtin function join:

A = DataFrame(Age = [27, 18, 28, 18, 28], Name = ["Jonah", "Alan", "Glory", "Popeye", "Alan"])

AB = join(A, B, on = :Name)

{{out}}

Following the task hint:

M = Dict(t[jb] => filter(l -> l[jb] == t[jb], B) for t in B)

return collect([a, b] for a in A for b in get(M, a[ja], ()))

for r in hashjoin(table1, 2, table2, 1)

println(r)

{{out}}

=={{header|Kotlin}}==

data class B(val character: String, val nemesis: String)

println("${c.rowB.character.padEnd(6)} ${c.rowB.nemesis}")

}

{{out}}

===Literal===

Lua tables are implemented with hash keys, so this task is a bit anti-idiomatic for Lua. That is, if you knew in advance that this would be the primary operation on the data, then you'd likely (re-)structure the data to directly support it. But, to comply with the intent of the task, the data here is initially structured as an indexed (rather than hash-keyed) array, <i>then</i> hashed dynamically. (it's analogous to the Python solution, where a list is immediately converted to a dictionary - but could have <i>began</i> as a dictionary)

local tabA = { recA(27,"Jonah"), recA(18,"Alan"), recA(28,"Glory"), recA(18,"Popeye"), recA(28,"Alan") }

for _,row in pairs(hashjoin(tabA, "Name", tabB, "Character")) do

print(row.A.Age, row.A.Name, row.B.Character, row.B.Nemesis)

{{out}}

<pre>27 Jonah Jonah Whales

===Idiomatic===

Or, at least semi-idiomatic / more-idiomatic, per comments above under the "Literal" implementation. Here, a "hashlist" structure is defined to allow retrieval either by indexed-list style (the database "rows") or by hashed-array-of-lists style (the database "index"), where the hash is maintained upon insert so that a later "hashjoin" operation becomes just a "join" operation. (Note that storage/performance issues are minimal, at least at this scale, as both the keys and rows in the hash are merely references, not copies.)

new = function(self,key)

return setmetatable({key=key, hash={}, list={}}, {__index=self})

for _,row in pairs(tabB:join(tabA)) do

print(row.B.Age, row.B.Name, row.A.Character, row.A.Nemesis)

{{out}}

<pre>27 Jonah Jonah Whales

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

Module HashJoin {

\\ normally we define variables when we put values to names

}

HashJoin

{{out}}

<pre >

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>

=={{header|Nim}}==

type

for row in hashJoin(table1, table2):

{{out}}

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

=={{header|Phix}}==

Phix dictionary keys must be unique, but storing/extending a sequence is no trouble, and in fact simplifies the scan phase.

<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>

<span style="color: #008080;">constant</span> <span style="color: #000000;">A</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{{</span><span style="color: #000000;">27</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"Jonah"</span><span style="color: #0000FF;">},</span>

<span style="color: #7060A8;">destroy_dict</span><span style="color: #0000FF;">(</span><span style="color: #000000;">MB</span><span style="color: #0000FF;">)</span>

<span style="color: #7060A8;">pp</span><span style="color: #0000FF;">(</span><span style="color: #000000;">C</span><span style="color: #0000FF;">,{</span><span style="color: #004600;">pp_Nest</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">})</span>

{{out}}

<pre>

=={{header|PHP}}==

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

// hash phase

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

print_r($row);

{{out}}

<pre>

=={{header|PicoLisp}}==

(27 . Jonah)

(18 . Alan)

(let? Y (car (idx 'M (cons (char (hash (cdr X))) (cdr X))))

(for Z (caar Y)

Output:

<pre>27 Jonah Jonah Spiders

=={{header|plainTeX}}==

Works with any TeX engine.

\def\quark{\quark}

\def\tabA{27:Jonah,18:Alan,28:Glory,18:Popeye,28:Alan}

}

\mergejoin

pdf or dvi output:

=={{header|Prolog}}==

person_age('Jonah', 27).

person_age('Alan', 18).

(person_age(Person, Age), character_nemisis(Person, Nemesis)),

format('~w\t~w\t~w\t\t~w\n', [Age, Person, Person, Nemesis])

{{out}}

<pre>

=={{header|PureBasic}}==

age.i

name.s

Next

Input()

{{out}}

<pre>Input A = 27 Jonah

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

{{works with|Rakudo|2016.07}}

my %hash := @b.classify(&b);

;

{{out}}

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

use std::hash::Hash;

println!("{:<3} | {:^14} | {}", age, name, nemesis);

}

{{out}}

<pre>Age | Character Name | Nemesis

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

{{works with|oracle}}

create table people (age number(3), name varchar2(30));

select 'Alan' , 'Zombies' from dual union all

select 'Glory', 'Buffy' from dual

Doing the join is trivial. Normally we would let the optimizer select the join method. However, to force a hash join, we can use an optimizer hint, USE_HASH.

{{out}}

{{trans|Rust}}

var map = [K: [B]]()

for (age, name, nemesis) in hashJoin(t1, t2) {

print("\(age) | \(name) | \(nemesis)")

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

=={{header|Wren}}==

{{libheader|Wren-fmt}}

class A {

}

}

{{out}}

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