同时在多个级别上合并散列阵列的复杂哈希值

Question

我意识到存在很多与此类似程度不同的问题。我已经搜索了很长时间（使用：[ruby]合并散列在关键）他们和我试图解决这个问题。在进入StackOverflow之前，我甚至和同事们一起分享了我的问题。这似乎是一个独特的问题，或者我们都只是盯着它看到一个明显的答案。

基本要求

1. 该解决方案必须与红宝石1.8.7标准库（没有宝石）工作。请随意另外说明其他版本的Ruby的解决方案，但这样做不会自动使一个答案比另一个更好。
2. 输入数据的结构不能由其提供者改变;整个数据结构按原样提供。如果需要暂时重新排列数据以提供最有效的答案，那么只要输出与下面所需的样本相匹配，就完全没问题。另外，该解决方案不能假定哈希中排序键的位置。
3. 源变量不能以任何方式改变;它在运行时是不可变的（这是检查），所以结果必须提供给一个新的变量。
4. 下面的示例数据是虚构的，但问题是真实的。还有其他级别的哈希数组也必须以相同的方式合并到其他键上;所以，最好的答案可以一般适用于任意级别的数据结构。
5. 最好的解决方案将易于阅读，维护，并适用于任意 - 虽然类似的数据结构。它不一定是单行代码，但是如果你可以满足一行Ruby代码中的所有要求，那么对你来说就是一种荣誉。

样本数据

如果我们认为是Apache Tomcat server.xml文件作为Ruby数据结构，而不是XML的，它可以为这个问题一个很好的模拟。进一步假设默认配置在上游合并 - 在交付给您之前 - 在稍后的某个操作使用结果数据结构之前，必须合并数据。源数据看起来非常像这样：

source = { 
    :Server => { 
    :'attribute.port'  => 8005, 
    :'attribute.shutdown' => 'SHUTDOWN', 
    :Listener    => [ 
     { :'attribute.className' => 'org.apache.catalina.startup.VersionLoggerListener' }, 
     { :'attribute.className' => 'org.apache.catalina.core.AprLifecycleListener', 
     :'attribute.SSLEngine' => 'off'}, 
     { :'attribute.className' => 'org.apache.catalina.core.JasperListener' }, 
     { :'attribute.className' => 'org.apache.catalina.core.JreMemoryLeakPreventionListener' }, 
     { :'attribute.className' => 'org.apache.catalina.core.AprLifecycleListener', 
     :'attribute.SSLEngine' => 'on'} 
    ], 
    :Service    => [ 
     { :'attribute.name' => 'Catalina', 
     :Connector  => [ 
      { :'attribute.port'  => 8080, 
      :'attribute.protocol' => 'HTTP/1.1'}, 
      { :'attribute.port'  => 8009, 
      :'attribute.protocol' => 'AJP/1.3'} 
     ], 
     :Engine   => { 
      :'attribute.name'   => 'Catalina', 
      :'attribute.defaultHost' => 'localhost', 
      :Realm     => { 
      :'attribute.className' => 'org.apache.catalina.realm.LockOutRealm', 
      :Realm     => [ 
       { :'attribute.className' => 'org.apache.catalina.realm.UserDatabaseRealm', 
       :'attribute.resourceName' => 'UserDatabase'} 
      ] 
      }, 
      :Host      => [ 
      { :'attribute.name'  => 'localhost', 
       :'attribute.appBase' => 'webapps', 
       :Valve    => [ 
       { :'attribute.className' => 'org.apache.catalina.valves.AccessLogValve', 
        :'attribute.directory' => 'logs'} 
       ] 
      } 
      ] 
     } 
     }, 
     { :'attribute.name' => 'Catalina', 
     :Connector  => [ 
      { :'attribute.port'   => 8080, 
      :'attribute.protocol'  => 'HTTP/1.1', 
      :'attribute.secure'  => true, 
      :'attribute.scheme'  => 'https', 
      :'attribute.proxyPort' => 443} 
     ] 
     }, 
     { :'attribute.name' => 'JSVCBridge', 
     :Connector  => [ 
      { :'attribute.port'   => 8010, 
      :'attribute.protocol'  => 'HTTP/2'} 
     ] 
     }, 
     { :'attribute.name' => 'Catalina', 
     :Engine   => { 
      :Host => [ 
      { :'attribute.name'  => 'localhost', 
       :Valve    => [ 
       { :'attribute.className'    => 'org.apache.catalina.valves.RemoteIpValve', 
        :'attribute.internalProxies'   => '*', 
        :'attribute.remoteIpHeader'   => 'X-Forwarded-For', 
        :'attribute.protocolHeader'   => 'X-Forwarded-Proto', 
        :'attribute.protocolHeaderHttpsValue' => 'https'} 
       ] 
      } 
      ] 
     } 
     } 
    ] 
    } 
} 

所面临的挑战是从它产生这样的结果：

result = { 
    :Server => { 
    :'attribute.port'  => 8005, 
    :'attribute.shutdown' => 'SHUTDOWN', 
    :Listener    => [ 
     { :'attribute.className' => 'org.apache.catalina.startup.VersionLoggerListener' }, 
     { :'attribute.className' => 'org.apache.catalina.core.AprLifecycleListener', 
     :'attribute.SSLEngine' => 'on'}, 
     { :'attribute.className' => 'org.apache.catalina.core.JasperListener' }, 
     { :'attribute.className' => 'org.apache.catalina.core.JreMemoryLeakPreventionListener' }, 
    ], 
    :Service    => [ 
     { :'attribute.name' => 'Catalina', 
     :Connector  => [ 
      { :'attribute.port'   => 8080, 
      :'attribute.protocol'  => 'HTTP/1.1', 
      :'attribute.secure'  => true, 
      :'attribute.scheme'  => 'https', 
      :'attribute.proxyPort' => 443}, 
      { :'attribute.port'  => 8009, 
      :'attribute.protocol' => 'AJP/1.3'} 
     ], 
     :Engine   => { 
      :'attribute.name'   => 'Catalina', 
      :'attribute.defaultHost' => 'localhost', 
      :Realm     => { 
      :'attribute.className' => 'org.apache.catalina.realm.LockOutRealm', 
      :Realm     => [ 
       { :'attribute.className' => 'org.apache.catalina.realm.UserDatabaseRealm', 
       :'attribute.resourceName' => 'UserDatabase'} 
      ] 
      }, 
      :Host      => [ 
      { :'attribute.name'  => 'localhost', 
       :'attribute.appBase' => 'webapps', 
       :Valve    => [ 
       { :'attribute.className' => 'org.apache.catalina.valves.AccessLogValve', 
        :'attribute.directory' => 'logs'}, 
       { :'attribute.className'    => 'org.apache.catalina.valves.RemoteIpValve', 
        :'attribute.internalProxies'   => '*', 
        :'attribute.remoteIpHeader'   => 'X-Forwarded-For', 
        :'attribute.protocolHeader'   => 'X-Forwarded-Proto', 
        :'attribute.protocolHeaderHttpsValue' => 'https'} 
       ] 
      } 
      ] 
     } 
     }, 
     { :'attribute.name' => 'JSVCBridge', 
     :Connector  => [ 
      { :'attribute.port'   => 8010, 
      :'attribute.protocol'  => 'HTTP/2'} 
     ] 
     } 
    ] 
    } 
} 

问题

我们需要source成为result。为了达到这个目的，:Listener被attribute.className合并; :Service合并attribute.name; :Connector的结果数组合并为attribute.port;等等。在数据结构中确定哈希数组的位置和每个要合并的关键点应该很容易地提供给解决方案。

这个问题的真正本质是找到一种通用的解决方案，它可以应用于像这样的复杂数据结构的多个任意级别，通过提供的密钥合并哈希数组，并生成合并后的结果提供位置和密钥对。

非常感谢您对本问题所持的时间和兴趣。根据您是基于散列的定数组中第一项的值合并散列假设

Answer 1

可能有冷凝这段代码的更优雅的方式，但我终于研制成功这个非常具有挑战性的问题的答案。虽然魔杖制造商的答案已接近尾声，但它是基于这样的假设：Hashes中的密钥顺序可预测且稳定。由于这是一个Ruby 1.8.7的问题，并且由于数据提供者没有这样的保证，我不得不采取不同的路径;我们必须通知合并引擎哪个键用于每个哈希数组。

我的（非优化的）解决方案所需的三个功能，并且定义了必要的合并键外部哈希：

1. deepMergeHash遍历散列，深深地扫描阵列
2. deepMergeArrayOfHashes执行对所需的合并的阵列的哈希值
3. subMergeHelper递归协助deepMergeArrayOfHashes

的吨里克不仅要递归地处理哈希，而且要始终知道哈希中的“现在”位置，以便可以知道必要的合并密钥。建立了一个确定位置的方法后，定义，查找和使用合并键变得微不足道。

解决方案

def subMergeHelper(lhs, rhs, mergeKeys, crumbTrail) 
    lhs.merge(rhs){|subKey, subLHS, subRHS| 
    mergeTrail = crumbTrail + ':' + subKey.to_s 
    case subLHS 
    when Array 
     deepMergeArrayOfHashes(subLHS + subRHS, mergeKeys, mergeTrail) 
    when Hash 
     subMergeHelper(subLHS, subRHS, mergeKeys, mergeTrail) 
    else 
     subRHS 
    end 
    } 
end 

def deepMergeArrayOfHashes(arrayOfHashes, mergeKeys, crumbTrail) 
    mergedArray = arrayOfHashes 
    if arrayOfHashes.all? {|e| e.class == Hash} 
    if mergeKeys.has_key?(crumbTrail) 
     mergeKey = mergeKeys[crumbTrail] 
     mergedArray = arrayOfHashes.group_by{|evalHash| evalHash[mergeKey.to_sym]}.map{|groupID, groupArrayOfHashes| 
     groupArrayOfHashes.reduce({}){|memoHash, evalHash| 
      memoHash.merge(evalHash){|hashKey, lhs, rhs| 
      deepTrail = crumbTrail + ':' + hashKey.to_s 
      case lhs 
      when Array 
       deepMergeArrayOfHashes(lhs + rhs, mergeKeys, deepTrail) 
      when Hash 
       subMergeHelper(lhs, rhs, mergeKeys, deepTrail) 
      else 
       rhs 
      end 
      } 
     } 
     } 
    else 
     $stderr.puts "[WARNING] deepMergeArrayOfHashes: received an Array of Hashes without merge key at #{crumbTrail}." 
    end 
    else 
    $stderr.puts "[WARNING] deepMergeArrayOfHashes: received an Array containing non-Hashes at #{crumbTrail}?" 
    end 
    return mergedArray 
end 

def deepMergeHash(hashConfig, mergeKeys, crumbTrail = '') 
    return hashConfig unless Hash == hashConfig.class 
    mergedConfig = {} 
    hashConfig.each{|nodeKey, nodeValue| 
    nodeCrumb = nodeKey.to_s 
    testTrail = crumbTrail + ':' + nodeCrumb 
    case nodeValue 
    when Hash 
     mergedConfig[nodeKey] = deepMergeHash(nodeValue, mergeKeys, testTrail) 
    when Array 
     mergedConfig[nodeKey] = deepMergeArrayOfHashes(nodeValue, mergeKeys, testTrail) 
    else 
     mergedConfig[nodeKey] = nodeValue 
    end 
    } 
    return mergedConfig 
end 

示例使用

在问题中的数据，我们现在可以：

mergeKeys = { 
    ':Server:Listener'     => 'attribute.className', 
    ':Server:Service'      => 'attribute.name', 
    ':Server:Service:Connector'   => 'attribute.port', 
    ':Server:Service:Engine:Host'   => 'attribute.name', 
    ':Server:Service:Engine:Host:Valve' => 'attribute.className', 
    ':Server:Service:Engine:Realm:Realm' => 'attribute.className' 
} 

mergedConfig = deepMergeHash(source, mergeKeys) 

我似乎无法执行成功平等测试，如(result == mergedConfig)，但目视检查图10显示它与result相同，只是某些键的顺序改变。我怀疑这是使用Ruby 1.8.x的一个副作用，可以接受这个问题。

快乐的编码，每个人都非常感谢您对本次讨论的兴趣。

Answer 2

解决方案下面给出：

def merge_ary(ary_hash) 
    # Lets not process something that is not array of hash 
    return ary_hash if not ary_hash.all? {|h| h.class == Hash } 

    # If array of hash, lets group them by value of first key 
    # Then, reduce the resultant group of hashes by merging them. 
    c = ary_hash.group_by {|h| h.values.first}.map do |k,v| 
    v_reduced = v.reduce({}) do |memo_hash, h| 
     memo_hash.merge(h) do |k, v1, v2| 
     v1.class == Array ? merge_ary(v1 + v2) : v2 
     end 
    end 
    [k, v_reduced] 
    end 
    return Hash[c].values 
end 

def merge_hash(hash) 
    t = hash.map do |k,v| 
    new_v = v 
    if v.class == Hash 
     new_v = merge_hash(v) 
    elsif v.class == Array 
     new_v = merge_ary(v) 
    end 
    [k,new_v] 
    end 
    return Hash[t] 
end 

# Test the output 
merge_hash(source) == result 
#=> true