해시 테이블 연습: 정규화 문자열 빈도와 등장 순서

'use strict';
class StringHashTable {
    constructor(capacity = 4) {
        if (! Number.isInteger(capacity) || capacity < 1) {
            throw new RangeError('capacity must be a positive integer');
        }
        this.buckets = Array.from( {
            length : capacity
        },() => []);
        this.size = 0;
    }
    normalize(key) {
        if (typeof key !== 'string') throw new TypeError('key must be a string');
        return key.normalize('NFC');
    }
    index(key, capacity = this.buckets.length) {
        let hash = 2166136261;
        for (const character of key) {
            hash = Math.imul(hash ^ character.codePointAt(0), 16777619) >>> 0;
        }
        return hash % capacity;
    }
    resize(capacity) {
        const next = Array.from( {
            length : capacity
        },() => []);
        for (const bucket of this.buckets) {
            for (const entry of bucket) {
                next[this.index(entry.key, capacity)].push(entry);
            }
        }
        this.buckets = next;
    }
    set(rawKey, value) {
        const key = this.normalize(rawKey);
        let bucket = this.buckets[this.index(key)];
        for (const entry of bucket) {
            if (entry.key === key) {
                entry.value = value;
                return this;
            }
        }
        if ((this.size + 1) / this.buckets.length > 0.75) {
            this.resize(this.buckets.length * 2);
            bucket = this.buckets[this.index(key)];
        }
        bucket.push( {
            key, value
        });
        this.size += 1;
        return this;
    }
    get(rawKey) {
        const key = this.normalize(rawKey);
        for (const entry of this.buckets[this.index(key)]) {
            if (entry.key === key) return {
                found : true, value : entry.value
            };
        }
        return {
            found : false
        };
    }
    delete(rawKey) {
        const key = this.normalize(rawKey);
        const bucket = this.buckets[this.index(key)];
        const index = bucket.findIndex(entry => entry.key === key);
        if (index === - 1) return false;
        bucket.splice(index, 1);
        this.size -= 1;
        return true;
    }
    entries() {
        const result = [];
        for (const bucket of this.buckets) {
            for (const entry of bucket) result.push([entry.key, entry.value]);
        }
        return result;
    }
}
function solve( {
    words
}) {
    const table = new StringHashTable();
    const order = [];
    for (const word of words) {
        const key = table.normalize(word);
        const previous = table.get(key);
        if (! previous.found) order.push(key);
        table.set(key, previous.found ? previous.value + 1 : 1);
    }
    return order.map(key => [key, table.get(key).value]);
}

import unicodedata
def solve(input):
    buckets=[[] for _ in range(4)]
    entries=[]
    for raw in input['words']:
        key=unicodedata.normalize('NFC',raw)
        bucket=buckets[hash(key)%len(buckets)]
        entry=next((e for e in bucket if e[0]==key),None)
        if entry is not None:
            entry[1]+=1
            continue
        if (len(entries)+1)*4>len(buckets)*3:
            buckets=[[] for _ in range(len(buckets)*2)]
            for e in entries: buckets[hash(e[0])%len(buckets)].append(e)
        entry=[key,1]
        entries.append(entry)
        buckets[hash(key)%len(buckets)].append(entry)
    return entries

import java.util.*;
import java.text.Normalizer;
class Solution {
    static class Entry {
        String key;
        int count = 1;
        Entry(String k) {
            key = k;
        }
    }
    List < List < Entry >> buckets(int n) {
        List < List < Entry >> b = new ArrayList < >();
        for (int i = 0; i < n; i++) b.add(new ArrayList < >());
        return b;
    }
    int index(String s, int n) {
        return Math.floorMod(s.hashCode(), n);
    }
    public Object[][] solve(String[] words) {
        List < List < Entry >> b = buckets(4);
        List < Entry > order = new ArrayList < >();
        for (String raw : words) {
            String key = Normalizer.normalize(raw, Normalizer.Form.NFC);
            Entry found = null;
            for (Entry e : b.get(index(key, b.size()))) if (e.key.equals(key)) {
                found = e;
                break;
            }
            if (found != null) {
                found.count++;
                continue;
            }
            if ((order.size() + 1) * 4 > b.size() * 3) {
                b = buckets(b.size() * 2);
                for (Entry e : order) b.get(index(e.key, b.size())).add(e);
            }
            Entry e = new Entry(key);
            order.add(e);
            b.get(index(key, b.size())).add(e);
        }
        Object[][] out = new Object[order.size()][2];
        for (int i = 0; i < out.length; i++) {
            out[i][0] = order.get(i).key;
            out[i][1] = order.get(i).count;
        }
        return out;
    }
}

#include <string>
#include <vector>
#include <utility>
#include <functional>
#include <stdexcept>
#include <unicode/unistr.h>
#include <unicode/normalizer2.h>
std::vector < std::pair < std::string, int >> solve(const std::vector < std::string > & words) {
    UErrorCode status = U_ZERO_ERROR;
    const auto * nfc = icu::Normalizer2::getNFCInstance(status);
    if (U_FAILURE(status)) throw std::runtime_error("ICU NFC unavailable");
    std::vector < std::pair < std::string, int >> entries;
    std::vector < std::vector < size_t >> buckets(4);
    std::hash < std::string > hash;
    for (const auto & raw : words) {
        icu::UnicodeString normalized;
        nfc->normalize(icu::UnicodeString::fromUTF8(raw), normalized, status);
        if (U_FAILURE(status)) throw std::runtime_error("NFC failed");
        std::string key;
        normalized.toUTF8String(key);
        bool found = false;
        for (size_t i : buckets[hash(key) % buckets.size()]) if (entries[i].first == key) {
            entries[i].second++;
            found = true;
            break;
        }
        if (found) continue;
        if ((entries.size() + 1) * 4 > buckets.size() * 3) {
            buckets = std::vector < std::vector < size_t >>(buckets.size() * 2);
            for (size_t i = 0; i < entries.size(); i++) buckets[hash(entries[i].first) % buckets.size()].push_back(i);
        }
        buckets[hash(key) % buckets.size()].push_back(entries.size());
        entries.push_back( {
            key, 1
        });
    }
    return entries;
}

using System;
using System.Text;
using System.Collections.Generic;
public class Solution {
    class Entry {
        public string key;
        public int count = 1;
        public Entry(string k) {
            key = k;
        }
    }
    List < Entry >[] Buckets(int n) {
        var b = new List < Entry >[n];
        for (int i = 0; i < n; i++) b[i] = new List < Entry >();
        return b;
    }
    int Index(string s, int n) {
        return(s.GetHashCode() & int.MaxValue) % n;
    }
    public object[][] Solve(string[] words) {
        var b = Buckets(4);
        var order = new List < Entry >();
        foreach(string raw in words) {
            string key = raw.Normalize(NormalizationForm.FormC);
            Entry found = null;
            foreach(var e in b[Index(key, b.Length)]) if (e.key == key) {
                found = e;
                break;
            }
            if (found != null) {
                found.count++;
                continue;
            }
            if ((order.Count + 1) * 4 > b.Length * 3) {
                b = Buckets(b.Length * 2);
                foreach(var old in order) b[Index(old.key, b.Length)].Add(old);
            }
            var fresh = new Entry(key);
            order.Add(fresh);
            b[Index(key, b.Length)].Add(fresh);
        }
        var result = new object[order.Count][];
        for (int i = 0; i < order.Count; i++) result[i] = new object[] {
            order[i].key, order[i].count
        };
        return result;
    }
}