--- id: 5956795bc9e2c415eb244de1 title: Хеш-приєднання challengeType: 5 forumTopicId: 302284 dashedName: hash-join --- # --description-- [ внутрішнє з'єднання ](https://www.freecodecamp.org/news/sql-join-types-inner-join-vs-outer-join-example/#how-to-use-an-inner-join-in-sql "news: SQL Join Types – Inner Join VS Outer Join Example#How to Use an INNER JOIN in SQL") — це операція, яка об'єднує дві таблиці даних в одну таблицю на основі відповідності значень стовпців. Найпростіший спосіб виконати цю операцію: [приєднання вкладеного циклу](https://en.wikipedia.org/wiki/Nested loop join "wp: Nested loop join")алгоритм, а більш масштабованою альтернативою є[хеш-приєднання](https://en.wikipedia.org/wiki/hash join "wp: hash join")алгоритм. Алгоритм "хеш-приєднання" складається з двох кроків:
  1. хеш фаза: Створіть ,багатофункціональної карти з однієї із двох таблиць, зіставляючи значення кожного стовпця до всіх рядків, що містять його.
  2. Приєднатися до фази: Скануйте іншу таблицю, знайдіть відповідні рядки, дивлячись у багатофункціональну карту, створену раніше.
В псевдокоді алгоритм може бути виражений так: 
нехай A = перша початкова таблиця (в ідеалі — найбільша)
нехай B = друга початкова таблиця (в ідеалі — найменша)
нехай jA = спільна колонка ID таблиці A
нехай jB = спільна колонка ID таблиці В
нехай MB = багатофункціональна карта для відображення від одиничних значень до кількох рядків таблиці B (починаючи з порожніх)
нехай C = вихідна таблиця (починаючи з порожніх)
для кожного ряду b таблиці B:
  місце b у багатофункціональній карті MB відповідно до b(jB)
для кожного ряду a у таблиці A:
  для кожного ряду b у багатофункціональній карті MB відповідно до a(jA):
    нехай c = ланцюжок рядків a і ряд b
    місце ряд c у таблиці C
# --instructions-- Реалізуйте алгоритм "хеш-приєднання" як функцію, та продемонструйте, що вона передає тестове значення, вказане нижче. Функція має приймати два масиви об'єктів і повертати масив комбінованих об’єктів. **Початкова інформація**
А =
Вік Ім'я
27 Йона
18 Алан
28 Глорія
18 Попай
28 Алан
B =
Персонаж Ворог
Йона Кити
Йона Павуки
Алан Привиди
Алан Зомбі
Глорія Баффі
jA = Ім'я (напр. колонка 1) jB = Персонаж (напр. колонка 0)
**Результат** | A_вік | A_ім'я | B_персонаж | B_ворог | | ----- | ------ | ---------- | ------- | | 27 | Йона | Йона | Кити | | 27 | Йона | Джон | Павуки | | 18 | Алан | Алан | Привиди | | 18 | Алан | Алан | Зомбі | | 28 | Глорі | Глорі | Баффі | | 28 | Алан | Алан | Привиди | | 28 | Алан | Алан | Зомбі | Порядок рядків у вихідній таблиці не є важливим. # --hints-- `hashJoin` має бути функцією. ```js assert(typeof hashJoin === 'function'); ``` `hashJoin([{ age: 27, name: "Jonah" }, { age: 18, name: "Alan" }, { age: 28, name: "Glory" }, { age: 18, name: "Popeye" }, { age: 28, name: "Alan" }], [{ character: "Jonah", nemesis: "Whales" }, { character: "Jonah", nemesis: "Spiders" }, { character: "Alan", nemesis: "Ghosts" }, { character:"Alan", nemesis: "Zombies" }, { character: "Glory", nemesis: "Buffy" }, { character: "Bob", nemesis: "foo" }])` має повернути `[{"A_age": 27,"A_name": "Jonah", "B_character": "Jonah", "B_nemesis": "Whales"}, {"A_age": 27,"A_name": "Jonah", "B_character": "Jonah", "B_nemesis": "Spiders"}, {"A_age": 18,"A_name": "Alan", "B_character": "Alan", "B_nemesis": "Ghosts"}, {"A_age": 18,"A_name": "Alan", "B_character": "Alan", "B_nemesis": "Zombies"}, {"A_age": 28,"A_name": "Glory", "B_character": "Glory", "B_nemesis": "Buffy"}, {"A_age": 28,"A_name": "Alan", "B_character": "Alan", "B_nemesis": "Ghosts"}, {"A_age": 28,"A_name": "Alan", "B_character": "Alan", "B_nemesis": "Zombies"}]` ```js assert.deepEqual(hashJoin(hash1, hash2), res); ``` # --seed-- ## --after-user-code-- ```js const hash1 = [ { age: 27, name: 'Jonah' }, { age: 18, name: 'Alan' }, { age: 28, name: 'Glory' }, { age: 18, name: 'Popeye' }, { age: 28, name: 'Alan' } ]; const hash2 = [ { character: 'Jonah', nemesis: 'Whales' }, { character: 'Jonah', nemesis: 'Spiders' }, { character: 'Alan', nemesis: 'Ghosts' }, { character: 'Alan', nemesis: 'Zombies' }, { character: 'Glory', nemesis: 'Buffy' }, { character: 'Bob', nemesis: 'foo' } ]; const res = [ { A_age: 27, A_name: 'Jonah', B_character: 'Jonah', B_nemesis: 'Whales' }, { A_age: 27, A_name: 'Jonah', B_character: 'Jonah', B_nemesis: 'Spiders' }, { A_age: 18, A_name: 'Alan', B_character: 'Alan', B_nemesis: 'Ghosts' }, { A_age: 18, A_name: 'Alan', B_character: 'Alan', B_nemesis: 'Zombies' }, { A_age: 28, A_name: 'Glory', B_character: 'Glory', B_nemesis: 'Buffy' }, { A_age: 28, A_name: 'Alan', B_character: 'Alan', B_nemesis: 'Ghosts' }, { A_age: 28, A_name: 'Alan', B_character: 'Alan', B_nemesis: 'Zombies' } ]; const bench1 = [{ name: 'u2v7v', num: 1 }, { name: 'n53c8', num: 10 }, { name: 'oysce', num: 9 }, { name: '0mto2s', num: 1 }, { name: 'vkh5id', num: 4 }, { name: '5od0cf', num: 8 }, { name: 'uuulue', num: 10 }, { name: '3rgsbi', num: 9 }, { name: 'kccv35r', num: 4 }, { name: '80un74', num: 9 }, { name: 'h4pp3', num: 6 }, { name: '51bit', num: 7 }, { name: 'j9ndf', num: 8 }, { name: 'vf3u1', num: 10 }, { name: 'g0bw0om', num: 10 }, { name: 'j031x', num: 7 }, { name: 'ij3asc', num: 9 }, { name: 'byv83y', num: 8 }, { name: 'bjzp4k', num: 4 }, { name: 'f3kbnm', num: 10 }]; const bench2 = [{ friend: 'o8b', num: 8 }, { friend: 'ye', num: 2 }, { friend: '32i', num: 5 }, { friend: 'uz', num: 3 }, { friend: 'a5k', num: 4 }, { friend: 'uad', num: 7 }, { friend: '3w5', num: 10 }, { friend: 'vw', num: 10 }, { friend: 'ah', num: 4 }, { friend: 'qv', num: 7 }, { friend: 'ozv', num: 2 }, { friend: '9ri', num: 10 }, { friend: '7nu', num: 4 }, { friend: 'w3', num: 9 }, { friend: 'tgp', num: 8 }, { friend: 'ibs', num: 1 }, { friend: 'ss7', num: 6 }, { friend: 'g44', num: 9 }, { friend: 'tab', num: 9 }, { friend: 'zem', num: 10 }]; ``` ## --seed-contents-- ```js function hashJoin(hash1, hash2) { return []; } ``` # --solutions-- ```js function hashJoin(hash1, hash2) { const hJoin = (tblA, tblB, strJoin) => { const [jA, jB] = strJoin.split('='); const M = tblB.reduce((a, x) => { const id = x[jB]; return ( a[id] ? a[id].push(x) : (a[id] = [x]), a ); }, {}); return tblA.reduce((a, x) => { const match = M[x[jA]]; return match ? ( a.concat(match.map(row => dictConcat(x, row))) ) : a; }, []); }; const dictConcat = (dctA, dctB) => { const ok = Object.keys; return ok(dctB).reduce( (a, k) => (a[`B_${k}`] = dctB[k]) && a, ok(dctA).reduce( (a, k) => (a[`A_${k}`] = dctA[k]) && a, {} ) ); }; return hJoin(hash1, hash2, 'name=character'); } ```