Refactor hash table code into its own module and use it for method_config as well as method_config_table.

27 files changed, 470 insertions, 151 deletions

diff --git a/BUILD b/BUILD
index d542561ec8..46adf28f29 100644
--- a/BUILD
+++ b/BUILD
@@ -239,6 +239,7 @@ cc_library(
     "src/core/lib/surface/server.h",
     "src/core/lib/transport/byte_stream.h",
     "src/core/lib/transport/connectivity_state.h",
+    "src/core/lib/transport/hashtable.h",
     "src/core/lib/transport/metadata.h",
     "src/core/lib/transport/metadata_batch.h",
     "src/core/lib/transport/static_metadata.h",
@@ -410,6 +411,7 @@ cc_library(
     "src/core/lib/surface/version.c",
     "src/core/lib/transport/byte_stream.c",
     "src/core/lib/transport/connectivity_state.c",
+    "src/core/lib/transport/hashtable.c",
     "src/core/lib/transport/metadata.c",
     "src/core/lib/transport/metadata_batch.c",
     "src/core/lib/transport/static_metadata.c",
@@ -642,6 +644,7 @@ cc_library(
     "src/core/lib/surface/server.h",
     "src/core/lib/transport/byte_stream.h",
     "src/core/lib/transport/connectivity_state.h",
+    "src/core/lib/transport/hashtable.h",
     "src/core/lib/transport/metadata.h",
     "src/core/lib/transport/metadata_batch.h",
     "src/core/lib/transport/static_metadata.h",
@@ -798,6 +801,7 @@ cc_library(
     "src/core/lib/surface/version.c",
     "src/core/lib/transport/byte_stream.c",
     "src/core/lib/transport/connectivity_state.c",
+    "src/core/lib/transport/hashtable.c",
     "src/core/lib/transport/metadata.c",
     "src/core/lib/transport/metadata_batch.c",
     "src/core/lib/transport/static_metadata.c",
@@ -1000,6 +1004,7 @@ cc_library(
     "src/core/lib/surface/server.h",
     "src/core/lib/transport/byte_stream.h",
     "src/core/lib/transport/connectivity_state.h",
+    "src/core/lib/transport/hashtable.h",
     "src/core/lib/transport/metadata.h",
     "src/core/lib/transport/metadata_batch.h",
     "src/core/lib/transport/static_metadata.h",
@@ -1148,6 +1153,7 @@ cc_library(
     "src/core/lib/surface/version.c",
     "src/core/lib/transport/byte_stream.c",
     "src/core/lib/transport/connectivity_state.c",
+    "src/core/lib/transport/hashtable.c",
     "src/core/lib/transport/metadata.c",
     "src/core/lib/transport/metadata_batch.c",
     "src/core/lib/transport/static_metadata.c",
@@ -1355,6 +1361,7 @@ cc_library(
     "src/core/lib/surface/server.h",
     "src/core/lib/transport/byte_stream.h",
     "src/core/lib/transport/connectivity_state.h",
+    "src/core/lib/transport/hashtable.h",
     "src/core/lib/transport/metadata.h",
     "src/core/lib/transport/metadata_batch.h",
     "src/core/lib/transport/static_metadata.h",
@@ -1480,6 +1487,7 @@ cc_library(
     "src/core/lib/surface/version.c",
     "src/core/lib/transport/byte_stream.c",
     "src/core/lib/transport/connectivity_state.c",
+    "src/core/lib/transport/hashtable.c",
     "src/core/lib/transport/metadata.c",
     "src/core/lib/transport/metadata_batch.c",
     "src/core/lib/transport/static_metadata.c",
@@ -1765,6 +1773,7 @@ cc_library(
     "src/core/lib/surface/server.h",
     "src/core/lib/transport/byte_stream.h",
     "src/core/lib/transport/connectivity_state.h",
+    "src/core/lib/transport/hashtable.h",
     "src/core/lib/transport/metadata.h",
     "src/core/lib/transport/metadata_batch.h",
     "src/core/lib/transport/static_metadata.h",
@@ -1885,6 +1894,7 @@ cc_library(
     "src/core/lib/surface/version.c",
     "src/core/lib/transport/byte_stream.c",
     "src/core/lib/transport/connectivity_state.c",
+    "src/core/lib/transport/hashtable.c",
     "src/core/lib/transport/metadata.c",
     "src/core/lib/transport/metadata_batch.c",
     "src/core/lib/transport/static_metadata.c",
@@ -2274,6 +2284,7 @@ objc_library(
     "src/core/lib/surface/version.c",
     "src/core/lib/transport/byte_stream.c",
     "src/core/lib/transport/connectivity_state.c",
+    "src/core/lib/transport/hashtable.c",
     "src/core/lib/transport/metadata.c",
     "src/core/lib/transport/metadata_batch.c",
     "src/core/lib/transport/static_metadata.c",
@@ -2485,6 +2496,7 @@ objc_library(
     "src/core/lib/surface/server.h",
     "src/core/lib/transport/byte_stream.h",
     "src/core/lib/transport/connectivity_state.h",
+    "src/core/lib/transport/hashtable.h",
     "src/core/lib/transport/metadata.h",
     "src/core/lib/transport/metadata_batch.h",
     "src/core/lib/transport/static_metadata.h",
diff --git a/CMakeLists.txt b/CMakeLists.txt
index 65a94bb995..39ea8906bf 100644
--- a/CMakeLists.txt
+++ b/CMakeLists.txt
@@ -376,6 +376,7 @@ add_library(grpc
   src/core/lib/surface/version.c
   src/core/lib/transport/byte_stream.c
   src/core/lib/transport/connectivity_state.c
+  src/core/lib/transport/hashtable.c
   src/core/lib/transport/metadata.c
   src/core/lib/transport/metadata_batch.c
   src/core/lib/transport/static_metadata.c
@@ -636,6 +637,7 @@ add_library(grpc_cronet
   src/core/lib/surface/version.c
   src/core/lib/transport/byte_stream.c
   src/core/lib/transport/connectivity_state.c
+  src/core/lib/transport/hashtable.c
   src/core/lib/transport/metadata.c
   src/core/lib/transport/metadata_batch.c
   src/core/lib/transport/static_metadata.c
@@ -868,6 +870,7 @@ add_library(grpc_unsecure
   src/core/lib/surface/version.c
   src/core/lib/transport/byte_stream.c
   src/core/lib/transport/connectivity_state.c
+  src/core/lib/transport/hashtable.c
   src/core/lib/transport/metadata.c
   src/core/lib/transport/metadata_batch.c
   src/core/lib/transport/static_metadata.c
@@ -1127,6 +1130,7 @@ add_library(grpc++
   src/core/lib/surface/version.c
   src/core/lib/transport/byte_stream.c
   src/core/lib/transport/connectivity_state.c
+  src/core/lib/transport/hashtable.c
   src/core/lib/transport/metadata.c
   src/core/lib/transport/metadata_batch.c
   src/core/lib/transport/static_metadata.c
@@ -1481,6 +1485,7 @@ add_library(grpc++_unsecure
   src/core/lib/surface/version.c
   src/core/lib/transport/byte_stream.c
   src/core/lib/transport/connectivity_state.c
+  src/core/lib/transport/hashtable.c
   src/core/lib/transport/metadata.c
   src/core/lib/transport/metadata_batch.c
   src/core/lib/transport/static_metadata.c
diff --git a/Makefile b/Makefile
index 2a22923442..674fe91ee7 100644
--- a/Makefile
+++ b/Makefile
@@ -2613,6 +2613,7 @@ LIBGRPC_SRC = \
     src/core/lib/surface/version.c \
     src/core/lib/transport/byte_stream.c \
     src/core/lib/transport/connectivity_state.c \
+    src/core/lib/transport/hashtable.c \
     src/core/lib/transport/metadata.c \
     src/core/lib/transport/metadata_batch.c \
     src/core/lib/transport/static_metadata.c \
@@ -2891,6 +2892,7 @@ LIBGRPC_CRONET_SRC = \
     src/core/lib/surface/version.c \
     src/core/lib/transport/byte_stream.c \
     src/core/lib/transport/connectivity_state.c \
+    src/core/lib/transport/hashtable.c \
     src/core/lib/transport/metadata.c \
     src/core/lib/transport/metadata_batch.c \
     src/core/lib/transport/static_metadata.c \
@@ -3158,6 +3160,7 @@ LIBGRPC_TEST_UTIL_SRC = \
     src/core/lib/surface/version.c \
     src/core/lib/transport/byte_stream.c \
     src/core/lib/transport/connectivity_state.c \
+    src/core/lib/transport/hashtable.c \
     src/core/lib/transport/metadata.c \
     src/core/lib/transport/metadata_batch.c \
     src/core/lib/transport/static_metadata.c \
@@ -3351,6 +3354,7 @@ LIBGRPC_UNSECURE_SRC = \
     src/core/lib/surface/version.c \
     src/core/lib/transport/byte_stream.c \
     src/core/lib/transport/connectivity_state.c \
+    src/core/lib/transport/hashtable.c \
     src/core/lib/transport/metadata.c \
     src/core/lib/transport/metadata_batch.c \
     src/core/lib/transport/static_metadata.c \
@@ -3693,6 +3697,7 @@ LIBGRPC++_SRC = \
     src/core/lib/surface/version.c \
     src/core/lib/transport/byte_stream.c \
     src/core/lib/transport/connectivity_state.c \
+    src/core/lib/transport/hashtable.c \
     src/core/lib/transport/metadata.c \
     src/core/lib/transport/metadata_batch.c \
     src/core/lib/transport/static_metadata.c \
@@ -4322,6 +4327,7 @@ LIBGRPC++_UNSECURE_SRC = \
     src/core/lib/surface/version.c \
     src/core/lib/transport/byte_stream.c \
     src/core/lib/transport/connectivity_state.c \
+    src/core/lib/transport/hashtable.c \
     src/core/lib/transport/metadata.c \
     src/core/lib/transport/metadata_batch.c \
     src/core/lib/transport/static_metadata.c \
diff --git a/binding.gyp b/binding.gyp
index 8aa153b878..88acd1786b 100644
--- a/binding.gyp
+++ b/binding.gyp
@@ -651,6 +651,7 @@
         'src/core/lib/surface/version.c',
         'src/core/lib/transport/byte_stream.c',
         'src/core/lib/transport/connectivity_state.c',
+        'src/core/lib/transport/hashtable.c',
         'src/core/lib/transport/metadata.c',
         'src/core/lib/transport/metadata_batch.c',
         'src/core/lib/transport/static_metadata.c',
diff --git a/build.yaml b/build.yaml
index fe2558eed3..7e95837ee9 100644
--- a/build.yaml
+++ b/build.yaml
@@ -243,6 +243,7 @@ filegroups:
   - src/core/lib/surface/server.h
   - src/core/lib/transport/byte_stream.h
   - src/core/lib/transport/connectivity_state.h
+  - src/core/lib/transport/hashtable.h
   - src/core/lib/transport/metadata.h
   - src/core/lib/transport/metadata_batch.h
   - src/core/lib/transport/static_metadata.h
@@ -336,6 +337,7 @@ filegroups:
   - src/core/lib/surface/version.c
   - src/core/lib/transport/byte_stream.c
   - src/core/lib/transport/connectivity_state.c
+  - src/core/lib/transport/hashtable.c
   - src/core/lib/transport/metadata.c
   - src/core/lib/transport/metadata_batch.c
   - src/core/lib/transport/static_metadata.c
diff --git a/config.m4 b/config.m4
index 6ee121df4e..f65f617f9a 100644
--- a/config.m4
+++ b/config.m4
@@ -170,6 +170,7 @@ if test "$PHP_GRPC" != "no"; then
     src/core/lib/surface/version.c \
     src/core/lib/transport/byte_stream.c \
     src/core/lib/transport/connectivity_state.c \
+    src/core/lib/transport/hashtable.c \
     src/core/lib/transport/metadata.c \
     src/core/lib/transport/metadata_batch.c \
     src/core/lib/transport/static_metadata.c \
diff --git a/gRPC-Core.podspec b/gRPC-Core.podspec
index 4581762bdf..ffa7ca0825 100644
--- a/gRPC-Core.podspec
+++ b/gRPC-Core.podspec
@@ -326,6 +326,7 @@ Pod::Spec.new do |s|
                       'src/core/lib/surface/server.h',
                       'src/core/lib/transport/byte_stream.h',
                       'src/core/lib/transport/connectivity_state.h',
+                      'src/core/lib/transport/hashtable.h',
                       'src/core/lib/transport/metadata.h',
                       'src/core/lib/transport/metadata_batch.h',
                       'src/core/lib/transport/static_metadata.h',
@@ -501,6 +502,7 @@ Pod::Spec.new do |s|
                       'src/core/lib/surface/version.c',
                       'src/core/lib/transport/byte_stream.c',
                       'src/core/lib/transport/connectivity_state.c',
+                      'src/core/lib/transport/hashtable.c',
                       'src/core/lib/transport/metadata.c',
                       'src/core/lib/transport/metadata_batch.c',
                       'src/core/lib/transport/static_metadata.c',
@@ -701,6 +703,7 @@ Pod::Spec.new do |s|
                               'src/core/lib/surface/server.h',
                               'src/core/lib/transport/byte_stream.h',
                               'src/core/lib/transport/connectivity_state.h',
+                              'src/core/lib/transport/hashtable.h',
                               'src/core/lib/transport/metadata.h',
                               'src/core/lib/transport/metadata_batch.h',
                               'src/core/lib/transport/static_metadata.h',
diff --git a/grpc.gemspec b/grpc.gemspec
index 2d4a8ddbcf..44cd7dd7f7 100755
--- a/grpc.gemspec
+++ b/grpc.gemspec
@@ -246,6 +246,7 @@ Gem::Specification.new do |s|
   s.files += %w( src/core/lib/surface/server.h )
   s.files += %w( src/core/lib/transport/byte_stream.h )
   s.files += %w( src/core/lib/transport/connectivity_state.h )
+  s.files += %w( src/core/lib/transport/hashtable.h )
   s.files += %w( src/core/lib/transport/metadata.h )
   s.files += %w( src/core/lib/transport/metadata_batch.h )
   s.files += %w( src/core/lib/transport/static_metadata.h )
@@ -421,6 +422,7 @@ Gem::Specification.new do |s|
   s.files += %w( src/core/lib/surface/version.c )
   s.files += %w( src/core/lib/transport/byte_stream.c )
   s.files += %w( src/core/lib/transport/connectivity_state.c )
+  s.files += %w( src/core/lib/transport/hashtable.c )
   s.files += %w( src/core/lib/transport/metadata.c )
   s.files += %w( src/core/lib/transport/metadata_batch.c )
   s.files += %w( src/core/lib/transport/static_metadata.c )
diff --git a/package.xml b/package.xml
index 8720216260..bf452c3b16 100644
--- a/package.xml
+++ b/package.xml
@@ -253,6 +253,7 @@
     <file baseinstalldir="/" name="src/core/lib/surface/server.h" role="src" />
     <file baseinstalldir="/" name="src/core/lib/transport/byte_stream.h" role="src" />
     <file baseinstalldir="/" name="src/core/lib/transport/connectivity_state.h" role="src" />
+    <file baseinstalldir="/" name="src/core/lib/transport/hashtable.h" role="src" />
     <file baseinstalldir="/" name="src/core/lib/transport/metadata.h" role="src" />
     <file baseinstalldir="/" name="src/core/lib/transport/metadata_batch.h" role="src" />
     <file baseinstalldir="/" name="src/core/lib/transport/static_metadata.h" role="src" />
@@ -428,6 +429,7 @@
     <file baseinstalldir="/" name="src/core/lib/surface/version.c" role="src" />
     <file baseinstalldir="/" name="src/core/lib/transport/byte_stream.c" role="src" />
     <file baseinstalldir="/" name="src/core/lib/transport/connectivity_state.c" role="src" />
+    <file baseinstalldir="/" name="src/core/lib/transport/hashtable.c" role="src" />
     <file baseinstalldir="/" name="src/core/lib/transport/metadata.c" role="src" />
     <file baseinstalldir="/" name="src/core/lib/transport/metadata_batch.c" role="src" />
     <file baseinstalldir="/" name="src/core/lib/transport/static_metadata.c" role="src" />
diff --git a/src/core/ext/client_config/method_config.c b/src/core/ext/client_config/method_config.c
index 989f776967..553a7be496 100644
--- a/src/core/ext/client_config/method_config.c
+++ b/src/core/ext/client_config/method_config.c
@@ -39,165 +39,214 @@
 #include <grpc/support/string_util.h>
 #include <grpc/support/time.h>
 
+#include "src/core/lib/transport/hashtable.h"
 #include "src/core/lib/transport/metadata.h"
 
 //
 // grpc_method_config
 //
 
+// bool vtable
+
+static void* bool_copy(void* valuep) {
+  bool value = *(bool*)valuep;
+  bool* new_value = gpr_malloc(sizeof(bool));
+  *new_value = value;
+  return new_value;
+}
+
+static int bool_cmp(void* v1, void* v2) {
+  bool b1 = *(bool*)v1;
+  bool b2 = *(bool*)v2;
+  if (!b1 && b2) return -1;
+  if (b1 && !b2) return 1;
+  return 0;
+}
+
+static grpc_hash_table_vtable bool_vtable = {gpr_free, bool_copy, bool_cmp};
+
+// timespec vtable
+
+static void* timespec_copy(void* valuep) {
+  gpr_timespec value = *(gpr_timespec*)valuep;
+  gpr_timespec* new_value = gpr_malloc(sizeof(gpr_timespec));
+  *new_value = value;
+  return new_value;
+}
+
+static int timespec_cmp(void* v1, void* v2) {
+  return gpr_time_cmp(*(gpr_timespec*)v1, *(gpr_timespec*)v2);
+}
+
+static grpc_hash_table_vtable timespec_vtable = {
+    gpr_free, timespec_copy, timespec_cmp};
+
+// int32 vtable
+
+static void* int32_copy(void* valuep) {
+  int32_t value = *(int32_t*)valuep;
+  int32_t* new_value = gpr_malloc(sizeof(int32_t));
+  *new_value = value;
+  return new_value;
+}
+
+static int int32_cmp(void* v1, void* v2) {
+  int32_t i1 = *(int32_t*)v1;
+  int32_t i2 = *(int32_t*)v2;
+  if (i1 < i2) return -1;
+  if (i1 > i2) return 1;
+  return 0;
+}
+
+static grpc_hash_table_vtable int32_vtable = {gpr_free, int32_copy, int32_cmp};
+
+// Hash table keys.
+#define GRPC_METHOD_CONFIG_WAIT_FOR_READY "grpc.wait_for_ready"  // bool
+#define GRPC_METHOD_CONFIG_TIMEOUT "grpc.timeout"  // gpr_timespec
+#define GRPC_METHOD_CONFIG_MAX_REQUEST_MESSAGE_BYTES \
+    "grpc.max_request_message_bytes"  // int32
+#define GRPC_METHOD_CONFIG_MAX_RESPONSE_MESSAGE_BYTES \
+    "grpc.max_response_message_bytes"  // int32
+
 struct grpc_method_config {
-  gpr_refcount refs;
-  bool* wait_for_ready;
-  gpr_timespec* timeout;
-  int32_t* max_request_message_bytes;
-  int32_t* max_response_message_bytes;
+  grpc_hash_table* table;
+  grpc_mdstr* wait_for_ready_key;
+  grpc_mdstr* timeout_key;
+  grpc_mdstr* max_request_message_bytes_key;
+  grpc_mdstr* max_response_message_bytes_key;
 };
 
 grpc_method_config* grpc_method_config_create(
     bool* wait_for_ready, gpr_timespec* timeout,
     int32_t* max_request_message_bytes, int32_t* max_response_message_bytes) {
-  grpc_method_config* config = gpr_malloc(sizeof(*config));
-  memset(config, 0, sizeof(*config));
-  gpr_ref_init(&config->refs, 1);
+  grpc_method_config* method_config = gpr_malloc(sizeof(grpc_method_config));
+  memset(method_config, 0, sizeof(grpc_method_config));
+  grpc_hash_table_entry entries[4];
+  size_t num_entries = 0;
   if (wait_for_ready != NULL) {
-    config->wait_for_ready = gpr_malloc(sizeof(*wait_for_ready));
-    *config->wait_for_ready = *wait_for_ready;
+    method_config->wait_for_ready_key =
+        grpc_mdstr_from_string(GRPC_METHOD_CONFIG_WAIT_FOR_READY);
+    entries[num_entries].key = method_config->wait_for_ready_key;
+    entries[num_entries].value = wait_for_ready;
+    entries[num_entries].vtable = &bool_vtable;
+    ++num_entries;
   }
   if (timeout != NULL) {
-    config->timeout = gpr_malloc(sizeof(*timeout));
-    *config->timeout = *timeout;
+    method_config->timeout_key =
+        grpc_mdstr_from_string(GRPC_METHOD_CONFIG_TIMEOUT);
+    entries[num_entries].key = method_config->timeout_key;
+    entries[num_entries].value = timeout;
+    entries[num_entries].vtable = &timespec_vtable;
+    ++num_entries;
   }
   if (max_request_message_bytes != NULL) {
-    config->max_request_message_bytes =
-        gpr_malloc(sizeof(*max_request_message_bytes));
-    *config->max_request_message_bytes = *max_request_message_bytes;
+    method_config->max_request_message_bytes_key =
+        grpc_mdstr_from_string(GRPC_METHOD_CONFIG_MAX_REQUEST_MESSAGE_BYTES);
+    entries[num_entries].key = method_config->max_request_message_bytes_key;
+    entries[num_entries].value = max_request_message_bytes;
+    entries[num_entries].vtable = &int32_vtable;
+    ++num_entries;
   }
   if (max_response_message_bytes != NULL) {
-    config->max_response_message_bytes =
-        gpr_malloc(sizeof(*max_response_message_bytes));
-    *config->max_response_message_bytes = *max_response_message_bytes;
+    method_config->max_response_message_bytes_key =
+        grpc_mdstr_from_string(GRPC_METHOD_CONFIG_MAX_RESPONSE_MESSAGE_BYTES);
+    entries[num_entries].key = method_config->max_response_message_bytes_key;
+    entries[num_entries].value = max_response_message_bytes;
+    entries[num_entries].vtable = &int32_vtable;
+    ++num_entries;
   }
-  return config;
+  method_config->table = grpc_hash_table_create(num_entries, entries);
+  return method_config;
 }
 
 grpc_method_config* grpc_method_config_ref(grpc_method_config* method_config) {
-  gpr_ref(&method_config->refs);
+  grpc_hash_table_ref(method_config->table);
   return method_config;
 }
 
 void grpc_method_config_unref(grpc_method_config* method_config) {
-  if (gpr_unref(&method_config->refs)) {
-    gpr_free(method_config->wait_for_ready);
-    gpr_free(method_config->timeout);
-    gpr_free(method_config->max_request_message_bytes);
-    gpr_free(method_config->max_response_message_bytes);
-    gpr_free(method_config);
+  if (grpc_hash_table_unref(method_config->table)) {
+    GRPC_MDSTR_UNREF(method_config->wait_for_ready_key);
+    GRPC_MDSTR_UNREF(method_config->timeout_key);
+    GRPC_MDSTR_UNREF(method_config->max_request_message_bytes_key);
+    GRPC_MDSTR_UNREF(method_config->max_response_message_bytes_key);
   }
 }
 
+int grpc_method_config_cmp(grpc_method_config* method_config1,
+                           grpc_method_config* method_config2) {
+  return grpc_hash_table_cmp(method_config1->table, method_config2->table);
+}
+
 bool* grpc_method_config_get_wait_for_ready(grpc_method_config* method_config) {
-  return method_config->wait_for_ready;
+  return grpc_hash_table_get(method_config->table,
+                             method_config->wait_for_ready_key);
 }
 
 gpr_timespec* grpc_method_config_get_timeout(
     grpc_method_config* method_config) {
-  return method_config->timeout;
+  return grpc_hash_table_get(method_config->table, method_config->timeout_key);
 }
 
 int32_t* grpc_method_config_get_max_request_message_bytes(
     grpc_method_config* method_config) {
-  return method_config->max_request_message_bytes;
+  return grpc_hash_table_get(method_config->table,
+                             method_config->max_request_message_bytes_key);
 }
 
 int32_t* grpc_method_config_get_max_response_message_bytes(
     grpc_method_config* method_config) {
-  return method_config->max_response_message_bytes;
+  return grpc_hash_table_get(method_config->table,
+                             method_config->max_response_message_bytes_key);
 }
 
 //
 // grpc_method_config_table
 //
 
-typedef struct grpc_method_config_table_entry {
-  grpc_mdstr* path;
-  grpc_method_config* method_config;
-} grpc_method_config_table_entry;
-
-#define METHOD_CONFIG_TABLE_SIZE 128
-struct grpc_method_config_table {
-  gpr_refcount refs;
-  grpc_method_config_table_entry entries[METHOD_CONFIG_TABLE_SIZE];
-};
-
-grpc_method_config_table* grpc_method_config_table_create() {
-  grpc_method_config_table* table = gpr_malloc(sizeof(*table));
-  memset(table, 0, sizeof(*table));
-  gpr_ref_init(&table->refs, 1);
-  return table;
+static void method_config_unref(void* valuep) {
+  grpc_method_config_unref(valuep);
 }
 
-grpc_method_config_table* grpc_method_config_table_ref(
-    grpc_method_config_table* table) {
-  if (table != NULL) gpr_ref(&table->refs);
-  return table;
+static void* method_config_ref(void* valuep) {
+  return grpc_method_config_ref(valuep);
 }
 
-void grpc_method_config_table_unref(grpc_method_config_table* table) {
-  if (table != NULL && gpr_unref(&table->refs)) {
-    for (size_t i = 0; i < GPR_ARRAY_SIZE(table->entries); ++i) {
-      grpc_method_config_table_entry* entry = &table->entries[i];
-      if (entry->path != NULL) {
-        GRPC_MDSTR_UNREF(entry->path);
-        grpc_method_config_unref(entry->method_config);
-      }
-    }
-  }
+static int method_config_cmp(void* valuep1, void* valuep2) {
+  return grpc_method_config_cmp(valuep1, valuep2);
 }
 
-// Helper function for insert and get operations that performs quadratic
-// probing (https://en.wikipedia.org/wiki/Quadratic_probing).
-static size_t grpc_method_config_table_find_index(
-    grpc_method_config_table* table, grpc_mdstr* path, bool find_empty) {
-  for (size_t i = 0; i < GPR_ARRAY_SIZE(table->entries); ++i) {
-    const size_t idx = (path->hash + i * i) % GPR_ARRAY_SIZE(table->entries);
-    if (table->entries[idx].path == NULL)
-      return find_empty ? idx : GPR_ARRAY_SIZE(table->entries);
-    if (table->entries[idx].path == path) return idx;
+static const grpc_hash_table_vtable method_config_table_vtable = {
+    method_config_unref, method_config_ref, method_config_cmp};
+
+grpc_method_config_table* grpc_method_config_table_create(
+    size_t num_entries, grpc_method_config_table_entry* entries) {
+  grpc_hash_table_entry hash_table_entries[num_entries];
+  for (size_t i = 0; i < num_entries; ++i) {
+    hash_table_entries[i].key = entries[i].method_name;
+    hash_table_entries[i].value = entries[i].method_config;
+    hash_table_entries[i].vtable = &method_config_table_vtable;
   }
-  return GPR_ARRAY_SIZE(table->entries) + 1;  // Not found.
+  return grpc_hash_table_create(num_entries, hash_table_entries);
 }
 
-static void grpc_method_config_table_insert(grpc_method_config_table* table,
-                                            grpc_mdstr* path,
-                                            grpc_method_config* config) {
-  const size_t idx =
-      grpc_method_config_table_find_index(table, path, true /* find_empty */);
-  // This can happen if the table is full.
-  GPR_ASSERT(idx != GPR_ARRAY_SIZE(table->entries));
-  grpc_method_config_table_entry* entry = &table->entries[idx];
-  entry->path = GRPC_MDSTR_REF(path);
-  entry->method_config = grpc_method_config_ref(config);
+grpc_method_config_table* grpc_method_config_table_ref(
+    grpc_method_config_table* table) {
+  return grpc_hash_table_ref(table);
 }
 
-static grpc_method_config* grpc_method_config_table_get(
-    grpc_method_config_table* table, grpc_mdstr* path) {
-  const size_t idx =
-      grpc_method_config_table_find_index(table, path, false /* find_empty */);
-  if (idx == GPR_ARRAY_SIZE(table->entries)) return NULL;  // Not found.
-  return table->entries[idx].method_config;
+void grpc_method_config_table_unref(grpc_method_config_table* table) {
+  grpc_hash_table_unref(table);
 }
 
-void grpc_method_config_table_add_method_config(
-    grpc_method_config_table* table, grpc_mdstr** paths, size_t num_paths,
-    grpc_method_config* method_config) {
-  for (size_t i = 0; i < num_paths; ++i) {
-    grpc_method_config_table_insert(table, paths[i], method_config);
-  }
+int grpc_method_config_table_cmp(grpc_method_config_table* table1,
+                                 grpc_method_config_table* table2) {
+  return grpc_hash_table_cmp(table1, table2);
 }
 
 grpc_method_config* grpc_method_config_table_get_method_config(
     grpc_method_config_table* table, grpc_mdstr* path) {
-  grpc_method_config* method_config = grpc_method_config_table_get(table, path);
+  grpc_method_config* method_config = grpc_hash_table_get(table, path);
   // If we didn't find a match for the path, try looking for a wildcard
   // entry (i.e., change "/service/method" to "/service/*").
   if (method_config == NULL) {
@@ -209,7 +258,7 @@ grpc_method_config* grpc_method_config_table_get_method_config(
     buf[len] = '*';
     buf[len + 1] = '\0';
     grpc_mdstr* wildcard_path = grpc_mdstr_from_string(buf);
-    method_config = grpc_method_config_table_get(table, wildcard_path);
+    method_config = grpc_hash_table_get(table, wildcard_path);
     GRPC_MDSTR_UNREF(wildcard_path);
   }
   return grpc_method_config_ref(method_config);
@@ -224,52 +273,7 @@ static void destroy_arg(void* p) {
 }
 
 static int cmp_arg(void* p1, void* p2) {
-  grpc_method_config_table* t1 = p1;
-  grpc_method_config_table* t2 = p2;
-  for (size_t i = 0; i < GPR_ARRAY_SIZE(t1->entries); ++i) {
-    grpc_method_config_table_entry* e1 = &t1->entries[i];
-    grpc_method_config_table_entry* e2 = &t2->entries[i];
-    // Compare paths by hash value.
-    if (e1->path->hash < e2->path->hash) return -1;
-    if (e1->path->hash > e2->path->hash) return 1;
-    // Compare wait_for_ready.
-    const bool wait_for_ready1 =
-        e1->method_config->wait_for_ready == NULL
-        ? false : *e1->method_config->wait_for_ready;
-    const bool wait_for_ready2 =
-        e2->method_config->wait_for_ready == NULL
-        ? false : *e2->method_config->wait_for_ready;
-    if (wait_for_ready1 < wait_for_ready2) return -1;
-    if (wait_for_ready1 > wait_for_ready2) return 1;
-    // Compare timeout.
-    const gpr_timespec timeout1 =
-        e1->method_config->timeout == NULL
-        ? gpr_inf_past(GPR_CLOCK_MONOTONIC) : *e1->method_config->timeout;
-    const gpr_timespec timeout2 =
-        e2->method_config->timeout == NULL
-        ? gpr_inf_past(GPR_CLOCK_MONOTONIC) : *e2->method_config->timeout;
-    const int timeout_result = gpr_time_cmp(timeout1, timeout2);
-    if (timeout_result != 0) return timeout_result;
-    // Compare max_request_message_bytes.
-    const int32_t max_request_message_bytes1 =
-        e1->method_config->max_request_message_bytes == NULL
-        ? -1 : *e1->method_config->max_request_message_bytes;
-    const int32_t max_request_message_bytes2 =
-        e2->method_config->max_request_message_bytes == NULL
-        ? -1 : *e2->method_config->max_request_message_bytes;
-    if (max_request_message_bytes1 < max_request_message_bytes2) return -1;
-    if (max_request_message_bytes1 > max_request_message_bytes2) return 1;
-    // Compare max_response_message_bytes.
-    const int32_t max_response_message_bytes1 =
-        e1->method_config->max_response_message_bytes == NULL
-        ? -1 : *e1->method_config->max_response_message_bytes;
-    const int32_t max_response_message_bytes2 =
-        e2->method_config->max_response_message_bytes == NULL
-        ? -1 : *e2->method_config->max_response_message_bytes;
-    if (max_response_message_bytes1 < max_response_message_bytes2) return -1;
-    if (max_response_message_bytes1 > max_response_message_bytes2) return 1;
-  }
-  return 0;
+  return grpc_method_config_table_cmp(p1, p2);
 }
 
 static grpc_arg_pointer_vtable arg_vtable = {copy_arg, destroy_arg, cmp_arg};
diff --git a/src/core/ext/client_config/method_config.h b/src/core/ext/client_config/method_config.h
index 2be0cd1006..e95a5583be 100644
--- a/src/core/ext/client_config/method_config.h
+++ b/src/core/ext/client_config/method_config.h
@@ -37,6 +37,7 @@
 #include <grpc/impl/codegen/gpr_types.h>
 #include <grpc/impl/codegen/grpc_types.h>
 
+#include "src/core/lib/transport/hashtable.h"
 #include "src/core/lib/transport/metadata.h"
 
 /// Per-method configuration.
@@ -50,6 +51,9 @@ grpc_method_config* grpc_method_config_create(
 grpc_method_config* grpc_method_config_ref(grpc_method_config* method_config);
 void grpc_method_config_unref(grpc_method_config* method_config);
 
+int grpc_method_config_cmp(grpc_method_config* method_config1,
+                           grpc_method_config* method_config2);
+
 /// These methods return NULL if the requested field is unset.
 /// The caller does NOT take ownership of the result.
 bool* grpc_method_config_get_wait_for_ready(grpc_method_config* method_config);
@@ -60,23 +64,26 @@ int32_t* grpc_method_config_get_max_response_message_bytes(
     grpc_method_config* method_config);
 
 /// A table of method configs.
-typedef struct grpc_method_config_table grpc_method_config_table;
+typedef grpc_hash_table grpc_method_config_table;
+
+typedef struct grpc_method_config_table_entry {
+  /// The name is of one of the following forms:
+  ///   service/method -- specifies exact service and method name
+  ///   service/*      -- matches all methods for the specified service
+  grpc_mdstr* method_name;
+  grpc_method_config* method_config;
+} grpc_method_config_table_entry;
 
-grpc_method_config_table* grpc_method_config_table_create();
+/// Takes new references to all keys and values in \a entries.
+grpc_method_config_table* grpc_method_config_table_create(
+    size_t num_entries, grpc_method_config_table_entry* entries);
 
 grpc_method_config_table* grpc_method_config_table_ref(
     grpc_method_config_table* table);
 void grpc_method_config_table_unref(grpc_method_config_table* table);
 
-/// Adds \a method_config to \a table.  \a paths indicates the set of path
-/// names for which this config applies.  Each name is of one of the
-/// following forms:
-///   service/method -- specifies exact service and method name
-///   service/*      -- matches all methods for the specified service
-/// Takes new references to all elements of \a paths and to \a method_config.
-void grpc_method_config_table_add_method_config(
-    grpc_method_config_table* table, grpc_mdstr** paths, size_t num_paths,
-    grpc_method_config* method_config);
+int grpc_method_config_table_cmp(grpc_method_config_table* table1,
+                                 grpc_method_config_table* table2);
 
 /// Returns NULL if the method has no config.
 /// Caller owns a reference to result.
diff --git a/src/core/lib/transport/hashtable.c b/src/core/lib/transport/hashtable.c
new file mode 100644
index 0000000000..89e2640969
--- /dev/null
+++ b/src/core/lib/transport/hashtable.c
@@ -0,0 +1,139 @@
+//
+// Copyright 2016, Google Inc.
+// All rights reserved.
+//
+// Redistribution and use in source and binary forms, with or without
+// modification, are permitted provided that the following conditions are
+// met:
+//
+//     * Redistributions of source code must retain the above copyright
+// notice, this list of conditions and the following disclaimer.
+//     * Redistributions in binary form must reproduce the above
+// copyright notice, this list of conditions and the following disclaimer
+// in the documentation and/or other materials provided with the
+// distribution.
+//     * Neither the name of Google Inc. nor the names of its
+// contributors may be used to endorse or promote products derived from
+// this software without specific prior written permission.
+//
+// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
+// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
+// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+//
+
+#include "src/core/lib/transport/hashtable.h"
+
+#include <stdbool.h>
+#include <string.h>
+
+#include <grpc/support/alloc.h>
+#include <grpc/support/log.h>
+
+#include "src/core/lib/transport/metadata.h"
+
+struct grpc_hash_table {
+  gpr_refcount refs;
+  size_t num_entries;
+  grpc_hash_table_entry* entries;
+};
+
+// Helper function for insert and get operations that performs quadratic
+// probing (https://en.wikipedia.org/wiki/Quadratic_probing).
+static size_t grpc_hash_table_find_index(
+    grpc_hash_table* table, grpc_mdstr* key, bool find_empty) {
+  for (size_t i = 0; i < table->num_entries; ++i) {
+    const size_t idx = (key->hash + i * i) % table->num_entries;
+    if (table->entries[idx].key == NULL)
+      return find_empty ? idx : table->num_entries;
+    if (table->entries[idx].key == key) return idx;
+  }
+  return table->num_entries;  // Not found.
+}
+
+static void grpc_hash_table_add(grpc_hash_table* table, grpc_mdstr* key,
+                                void* value,
+                                const grpc_hash_table_vtable* vtable) {
+  GPR_ASSERT(value != NULL);
+  const size_t idx =
+      grpc_hash_table_find_index(table, key, true /* find_empty */);
+  // This can happen if the table is full.
+  GPR_ASSERT(idx != table->num_entries);
+  grpc_hash_table_entry* entry = &table->entries[idx];
+  entry->key = GRPC_MDSTR_REF(key);
+  entry->value = vtable->copy_value(value);
+  entry->vtable = vtable;
+}
+
+grpc_hash_table* grpc_hash_table_create(size_t num_entries,
+                                        grpc_hash_table_entry* entries) {
+  grpc_hash_table* table = gpr_malloc(sizeof(*table));
+  memset(table, 0, sizeof(*table));
+  gpr_ref_init(&table->refs, 1);
+  // Quadratic chaining gets best performance when the table is no more
+  // than half full.
+  table->num_entries = num_entries * 2;
+  const size_t entry_size = sizeof(grpc_hash_table_entry) * table->num_entries;
+  table->entries = gpr_malloc(entry_size);
+  memset(table->entries, 0, entry_size);
+  for (size_t i = 0; i < num_entries; ++i) {
+    grpc_hash_table_entry* entry = &entries[i];
+    grpc_hash_table_add(table, entry->key, entry->value, entry->vtable);
+  }
+  return table;
+}
+
+grpc_hash_table* grpc_hash_table_ref(grpc_hash_table* table) {
+  if (table != NULL) gpr_ref(&table->refs);
+  return table;
+}
+
+int grpc_hash_table_unref(grpc_hash_table* table) {
+  if (table != NULL && gpr_unref(&table->refs)) {
+    for (size_t i = 0; i < table->num_entries; ++i) {
+      grpc_hash_table_entry* entry = &table->entries[i];
+      if (entry->key != NULL) {
+        GRPC_MDSTR_UNREF(entry->key);
+        entry->vtable->destroy_value(entry->value);
+      }
+    }
+    gpr_free(table->entries);
+    gpr_free(table);
+    return 1;
+  }
+  return 0;
+}
+
+void* grpc_hash_table_get(grpc_hash_table* table, grpc_mdstr* key) {
+  const size_t idx =
+      grpc_hash_table_find_index(table, key, false /* find_empty */);
+  if (idx == table->num_entries) return NULL;  // Not found.
+  return table->entries[idx].value;
+}
+
+int grpc_hash_table_cmp(grpc_hash_table* table1, grpc_hash_table* table2) {
+  // Compare by num_entries.
+  if (table1->num_entries < table2->num_entries) return -1;
+  if (table1->num_entries > table2->num_entries) return 1;
+  for (size_t i = 0; i < table1->num_entries; ++i) {
+    grpc_hash_table_entry* e1 = &table1->entries[i];
+    grpc_hash_table_entry* e2 = &table2->entries[i];
+    // Compare keys by hash value.
+    if (e1->key->hash < e2->key->hash) return -1;
+    if (e1->key->hash > e2->key->hash) return 1;
+    // Compare by vtable (pointer equality).
+    if (e1->vtable < e2->vtable) return -1;
+    if (e1->vtable > e2->vtable) return 1;
+    // Compare values via vtable.
+    const int value_result = e1->vtable->compare_value(e1->value, e2->value);
+    if (value_result != 0) return value_result;
+  }
+  return 0;
+}
diff --git a/src/core/lib/transport/hashtable.h b/src/core/lib/transport/hashtable.h
new file mode 100644
index 0000000000..93f0642c17
--- /dev/null
+++ b/src/core/lib/transport/hashtable.h
@@ -0,0 +1,82 @@
+/*
+ * Copyright 2016, Google Inc.
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions are
+ * met:
+ *
+ *     * Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ *     * Redistributions in binary form must reproduce the above
+ * copyright notice, this list of conditions and the following disclaimer
+ * in the documentation and/or other materials provided with the
+ * distribution.
+ *     * Neither the name of Google Inc. nor the names of its
+ * contributors may be used to endorse or promote products derived from
+ * this software without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+ * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+ * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+ * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
+ * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+ * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
+ * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+ * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+ * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#ifndef GRPC_CORE_LIB_TRANSPORT_HASHTABLE_H
+#define GRPC_CORE_LIB_TRANSPORT_HASHTABLE_H
+
+#include "src/core/lib/transport/metadata.h"
+
+/** Hash table implementation.
+ *
+ * This implementation uses open addressing
+ * (https://en.wikipedia.org/wiki/Open_addressing) with quadratic
+ * probing (https://en.wikipedia.org/wiki/Quadratic_probing).
+ * This means that the hash table is of fixed size and cannot contain
+ * more than that number of elements.
+ *
+ * The keys are grpc_mdstr objects.  The values are arbitrary pointers
+ * with a common vtable.
+ *
+ * Hash tables are intentionally immutable, to avoid the need for locking.
+ */
+
+typedef struct grpc_hash_table grpc_hash_table;
+
+typedef struct grpc_hash_table_vtable {
+  void (*destroy_value)(void* value);
+  void* (*copy_value)(void* value);
+  int (*compare_value)(void* value1, void* value2);
+} grpc_hash_table_vtable;
+
+typedef struct grpc_hash_table_entry {
+  grpc_mdstr* key;
+  void* value;  /* Must not be NULL. */
+  const grpc_hash_table_vtable* vtable;
+} grpc_hash_table_entry;
+
+/** Creates a new hash table of containing \a entries, which is an array
+    of length \a num_entries.
+    Creates its own copy of all keys and values from \a entries. */
+grpc_hash_table* grpc_hash_table_create(size_t num_entries,
+                                        grpc_hash_table_entry* entries);
+
+grpc_hash_table* grpc_hash_table_ref(grpc_hash_table* table);
+/** Returns 1 when \a table is destroyed. */
+int grpc_hash_table_unref(grpc_hash_table* table);
+
+/** Returns the value from \a table associated with \a key.
+    Returns NULL if \a key is not found. */
+void* grpc_hash_table_get(grpc_hash_table* table, grpc_mdstr* key);
+
+/** Compares two hash tables. */
+int grpc_hash_table_cmp(grpc_hash_table* table1, grpc_hash_table* table2);
+
+#endif /* GRPC_CORE_LIB_TRANSPORT_HASHTABLE_H */
diff --git a/src/python/grpcio/grpc_core_dependencies.py b/src/python/grpcio/grpc_core_dependencies.py
index f9308ba7a5..315d469a15 100644
--- a/src/python/grpcio/grpc_core_dependencies.py
+++ b/src/python/grpcio/grpc_core_dependencies.py
@@ -164,6 +164,7 @@ CORE_SOURCE_FILES = [
   'src/core/lib/surface/version.c',
   'src/core/lib/transport/byte_stream.c',
   'src/core/lib/transport/connectivity_state.c',
+  'src/core/lib/transport/hashtable.c',
   'src/core/lib/transport/metadata.c',
   'src/core/lib/transport/metadata_batch.c',
   'src/core/lib/transport/static_metadata.c',
diff --git a/tools/doxygen/Doxyfile.c++.internal b/tools/doxygen/Doxyfile.c++.internal
index ce21a4ea00..1619194d4a 100644
--- a/tools/doxygen/Doxyfile.c++.internal
+++ b/tools/doxygen/Doxyfile.c++.internal
@@ -947,6 +947,7 @@ src/core/lib/surface/lame_client.h \
 src/core/lib/surface/server.h \
 src/core/lib/transport/byte_stream.h \
 src/core/lib/transport/connectivity_state.h \
+src/core/lib/transport/hashtable.h \
 src/core/lib/transport/metadata.h \
 src/core/lib/transport/metadata_batch.h \
 src/core/lib/transport/static_metadata.h \
@@ -1072,6 +1073,7 @@ src/core/lib/surface/validate_metadata.c \
 src/core/lib/surface/version.c \
 src/core/lib/transport/byte_stream.c \
 src/core/lib/transport/connectivity_state.c \
+src/core/lib/transport/hashtable.c \
 src/core/lib/transport/metadata.c \
 src/core/lib/transport/metadata_batch.c \
 src/core/lib/transport/static_metadata.c \
diff --git a/tools/doxygen/Doxyfile.core.internal b/tools/doxygen/Doxyfile.core.internal
index 9ea6695f24..c9317396f6 100644
--- a/tools/doxygen/Doxyfile.core.internal
+++ b/tools/doxygen/Doxyfile.core.internal
@@ -863,6 +863,7 @@ src/core/lib/surface/lame_client.h \
 src/core/lib/surface/server.h \
 src/core/lib/transport/byte_stream.h \
 src/core/lib/transport/connectivity_state.h \
+src/core/lib/transport/hashtable.h \
 src/core/lib/transport/metadata.h \
 src/core/lib/transport/metadata_batch.h \
 src/core/lib/transport/static_metadata.h \
@@ -1038,6 +1039,7 @@ src/core/lib/surface/validate_metadata.c \
 src/core/lib/surface/version.c \
 src/core/lib/transport/byte_stream.c \
 src/core/lib/transport/connectivity_state.c \
+src/core/lib/transport/hashtable.c \
 src/core/lib/transport/metadata.c \
 src/core/lib/transport/metadata_batch.c \
 src/core/lib/transport/static_metadata.c \
diff --git a/tools/run_tests/sources_and_headers.json b/tools/run_tests/sources_and_headers.json
index f6889c8f3a..0fe6cdf6b9 100644
--- a/tools/run_tests/sources_and_headers.json
+++ b/tools/run_tests/sources_and_headers.json
@@ -6049,6 +6049,7 @@
       "src/core/lib/surface/server.h", 
       "src/core/lib/transport/byte_stream.h", 
       "src/core/lib/transport/connectivity_state.h", 
+      "src/core/lib/transport/hashtable.h", 
       "src/core/lib/transport/metadata.h", 
       "src/core/lib/transport/metadata_batch.h", 
       "src/core/lib/transport/static_metadata.h", 
@@ -6229,6 +6230,8 @@
       "src/core/lib/transport/byte_stream.h", 
       "src/core/lib/transport/connectivity_state.c", 
       "src/core/lib/transport/connectivity_state.h", 
+      "src/core/lib/transport/hashtable.c", 
+      "src/core/lib/transport/hashtable.h", 
       "src/core/lib/transport/metadata.c", 
       "src/core/lib/transport/metadata.h", 
       "src/core/lib/transport/metadata_batch.c", 
diff --git a/vsprojects/vcxproj/grpc++/grpc++.vcxproj b/vsprojects/vcxproj/grpc++/grpc++.vcxproj
index 88ddecf426..92a7e02e52 100644
--- a/vsprojects/vcxproj/grpc++/grpc++.vcxproj
+++ b/vsprojects/vcxproj/grpc++/grpc++.vcxproj
@@ -447,6 +447,7 @@
     <ClInclude Include="$(SolutionDir)\..\src\core\lib\surface\server.h" />
     <ClInclude Include="$(SolutionDir)\..\src\core\lib\transport\byte_stream.h" />
     <ClInclude Include="$(SolutionDir)\..\src\core\lib\transport\connectivity_state.h" />
+    <ClInclude Include="$(SolutionDir)\..\src\core\lib\transport\hashtable.h" />
     <ClInclude Include="$(SolutionDir)\..\src\core\lib\transport\metadata.h" />
     <ClInclude Include="$(SolutionDir)\..\src\core\lib\transport\metadata_batch.h" />
     <ClInclude Include="$(SolutionDir)\..\src\core\lib\transport\static_metadata.h" />
@@ -693,6 +694,8 @@
     </ClCompile>
     <ClCompile Include="$(SolutionDir)\..\src\core\lib\transport\connectivity_state.c">
     </ClCompile>
+    <ClCompile Include="$(SolutionDir)\..\src\core\lib\transport\hashtable.c">
+    </ClCompile>
     <ClCompile Include="$(SolutionDir)\..\src\core\lib\transport\metadata.c">
     </ClCompile>
     <ClCompile Include="$(SolutionDir)\..\src\core\lib\transport\metadata_batch.c">
diff --git a/vsprojects/vcxproj/grpc++/grpc++.vcxproj.filters b/vsprojects/vcxproj/grpc++/grpc++.vcxproj.filters
index a6616449d3..9282b52eef 100644
--- a/vsprojects/vcxproj/grpc++/grpc++.vcxproj.filters
+++ b/vsprojects/vcxproj/grpc++/grpc++.vcxproj.filters
@@ -358,6 +358,9 @@
     <ClCompile Include="$(SolutionDir)\..\src\core\lib\transport\connectivity_state.c">
       <Filter>src\core\lib\transport</Filter>
     </ClCompile>
+    <ClCompile Include="$(SolutionDir)\..\src\core\lib\transport\hashtable.c">
+      <Filter>src\core\lib\transport</Filter>
+    </ClCompile>
     <ClCompile Include="$(SolutionDir)\..\src\core\lib\transport\metadata.c">
       <Filter>src\core\lib\transport</Filter>
     </ClCompile>
@@ -944,6 +947,9 @@
     <ClInclude Include="$(SolutionDir)\..\src\core\lib\transport\connectivity_state.h">
       <Filter>src\core\lib\transport</Filter>
     </ClInclude>
+    <ClInclude Include="$(SolutionDir)\..\src\core\lib\transport\hashtable.h">
+      <Filter>src\core\lib\transport</Filter>
+    </ClInclude>
     <ClInclude Include="$(SolutionDir)\..\src\core\lib\transport\metadata.h">
       <Filter>src\core\lib\transport</Filter>
     </ClInclude>
diff --git a/vsprojects/vcxproj/grpc++_unsecure/grpc++_unsecure.vcxproj b/vsprojects/vcxproj/grpc++_unsecure/grpc++_unsecure.vcxproj
index 99cee2830a..0270fe4836 100644
--- a/vsprojects/vcxproj/grpc++_unsecure/grpc++_unsecure.vcxproj
+++ b/vsprojects/vcxproj/grpc++_unsecure/grpc++_unsecure.vcxproj
@@ -443,6 +443,7 @@
     <ClInclude Include="$(SolutionDir)\..\src\core\lib\surface\server.h" />
     <ClInclude Include="$(SolutionDir)\..\src\core\lib\transport\byte_stream.h" />
     <ClInclude Include="$(SolutionDir)\..\src\core\lib\transport\connectivity_state.h" />
+    <ClInclude Include="$(SolutionDir)\..\src\core\lib\transport\hashtable.h" />
     <ClInclude Include="$(SolutionDir)\..\src\core\lib\transport\metadata.h" />
     <ClInclude Include="$(SolutionDir)\..\src\core\lib\transport\metadata_batch.h" />
     <ClInclude Include="$(SolutionDir)\..\src\core\lib\transport\static_metadata.h" />
@@ -679,6 +680,8 @@
     </ClCompile>
     <ClCompile Include="$(SolutionDir)\..\src\core\lib\transport\connectivity_state.c">
     </ClCompile>
+    <ClCompile Include="$(SolutionDir)\..\src\core\lib\transport\hashtable.c">
+    </ClCompile>
     <ClCompile Include="$(SolutionDir)\..\src\core\lib\transport\metadata.c">
     </ClCompile>
     <ClCompile Include="$(SolutionDir)\..\src\core\lib\transport\metadata_batch.c">
diff --git a/vsprojects/vcxproj/grpc++_unsecure/grpc++_unsecure.vcxproj.filters b/vsprojects/vcxproj/grpc++_unsecure/grpc++_unsecure.vcxproj.filters
index e1b6b2f327..8863237f43 100644
--- a/vsprojects/vcxproj/grpc++_unsecure/grpc++_unsecure.vcxproj.filters
+++ b/vsprojects/vcxproj/grpc++_unsecure/grpc++_unsecure.vcxproj.filters
@@ -343,6 +343,9 @@
     <ClCompile Include="$(SolutionDir)\..\src\core\lib\transport\connectivity_state.c">
       <Filter>src\core\lib\transport</Filter>
     </ClCompile>
+    <ClCompile Include="$(SolutionDir)\..\src\core\lib\transport\hashtable.c">
+      <Filter>src\core\lib\transport</Filter>
+    </ClCompile>
     <ClCompile Include="$(SolutionDir)\..\src\core\lib\transport\metadata.c">
       <Filter>src\core\lib\transport</Filter>
     </ClCompile>
@@ -917,6 +920,9 @@
     <ClInclude Include="$(SolutionDir)\..\src\core\lib\transport\connectivity_state.h">
       <Filter>src\core\lib\transport</Filter>
     </ClInclude>
+    <ClInclude Include="$(SolutionDir)\..\src\core\lib\transport\hashtable.h">
+      <Filter>src\core\lib\transport</Filter>
+    </ClInclude>
     <ClInclude Include="$(SolutionDir)\..\src\core\lib\transport\metadata.h">
       <Filter>src\core\lib\transport</Filter>
     </ClInclude>
diff --git a/vsprojects/vcxproj/grpc/grpc.vcxproj b/vsprojects/vcxproj/grpc/grpc.vcxproj
index ba2174f429..b2352d74f4 100644
--- a/vsprojects/vcxproj/grpc/grpc.vcxproj
+++ b/vsprojects/vcxproj/grpc/grpc.vcxproj
@@ -372,6 +372,7 @@
     <ClInclude Include="$(SolutionDir)\..\src\core\lib\surface\server.h" />
     <ClInclude Include="$(SolutionDir)\..\src\core\lib\transport\byte_stream.h" />
     <ClInclude Include="$(SolutionDir)\..\src\core\lib\transport\connectivity_state.h" />
+    <ClInclude Include="$(SolutionDir)\..\src\core\lib\transport\hashtable.h" />
     <ClInclude Include="$(SolutionDir)\..\src\core\lib\transport\metadata.h" />
     <ClInclude Include="$(SolutionDir)\..\src\core\lib\transport\metadata_batch.h" />
     <ClInclude Include="$(SolutionDir)\..\src\core\lib\transport\static_metadata.h" />
@@ -636,6 +637,8 @@
     </ClCompile>
     <ClCompile Include="$(SolutionDir)\..\src\core\lib\transport\connectivity_state.c">
     </ClCompile>
+    <ClCompile Include="$(SolutionDir)\..\src\core\lib\transport\hashtable.c">
+    </ClCompile>
     <ClCompile Include="$(SolutionDir)\..\src\core\lib\transport\metadata.c">
     </ClCompile>
     <ClCompile Include="$(SolutionDir)\..\src\core\lib\transport\metadata_batch.c">
diff --git a/vsprojects/vcxproj/grpc/grpc.vcxproj.filters b/vsprojects/vcxproj/grpc/grpc.vcxproj.filters
index ee3e7a85d3..ee7825ae88 100644
--- a/vsprojects/vcxproj/grpc/grpc.vcxproj.filters
+++ b/vsprojects/vcxproj/grpc/grpc.vcxproj.filters
@@ -262,6 +262,9 @@
     <ClCompile Include="$(SolutionDir)\..\src\core\lib\transport\connectivity_state.c">
       <Filter>src\core\lib\transport</Filter>
     </ClCompile>
+    <ClCompile Include="$(SolutionDir)\..\src\core\lib\transport\hashtable.c">
+      <Filter>src\core\lib\transport</Filter>
+    </ClCompile>
     <ClCompile Include="$(SolutionDir)\..\src\core\lib\transport\metadata.c">
       <Filter>src\core\lib\transport</Filter>
     </ClCompile>
@@ -902,6 +905,9 @@
     <ClInclude Include="$(SolutionDir)\..\src\core\lib\transport\connectivity_state.h">
       <Filter>src\core\lib\transport</Filter>
     </ClInclude>
+    <ClInclude Include="$(SolutionDir)\..\src\core\lib\transport\hashtable.h">
+      <Filter>src\core\lib\transport</Filter>
+    </ClInclude>
     <ClInclude Include="$(SolutionDir)\..\src\core\lib\transport\metadata.h">
       <Filter>src\core\lib\transport</Filter>
     </ClInclude>
diff --git a/vsprojects/vcxproj/grpc_test_util/grpc_test_util.vcxproj b/vsprojects/vcxproj/grpc_test_util/grpc_test_util.vcxproj
index 21d9fc9529..f09be1528b 100644
--- a/vsprojects/vcxproj/grpc_test_util/grpc_test_util.vcxproj
+++ b/vsprojects/vcxproj/grpc_test_util/grpc_test_util.vcxproj
@@ -264,6 +264,7 @@
     <ClInclude Include="$(SolutionDir)\..\src\core\lib\surface\server.h" />
     <ClInclude Include="$(SolutionDir)\..\src\core\lib\transport\byte_stream.h" />
     <ClInclude Include="$(SolutionDir)\..\src\core\lib\transport\connectivity_state.h" />
+    <ClInclude Include="$(SolutionDir)\..\src\core\lib\transport\hashtable.h" />
     <ClInclude Include="$(SolutionDir)\..\src\core\lib\transport\metadata.h" />
     <ClInclude Include="$(SolutionDir)\..\src\core\lib\transport\metadata_batch.h" />
     <ClInclude Include="$(SolutionDir)\..\src\core\lib\transport\static_metadata.h" />
@@ -480,6 +481,8 @@
     </ClCompile>
     <ClCompile Include="$(SolutionDir)\..\src\core\lib\transport\connectivity_state.c">
     </ClCompile>
+    <ClCompile Include="$(SolutionDir)\..\src\core\lib\transport\hashtable.c">
+    </ClCompile>
     <ClCompile Include="$(SolutionDir)\..\src\core\lib\transport\metadata.c">
     </ClCompile>
     <ClCompile Include="$(SolutionDir)\..\src\core\lib\transport\metadata_batch.c">
diff --git a/vsprojects/vcxproj/grpc_test_util/grpc_test_util.vcxproj.filters b/vsprojects/vcxproj/grpc_test_util/grpc_test_util.vcxproj.filters
index 09a32482cd..7be3b76d23 100644
--- a/vsprojects/vcxproj/grpc_test_util/grpc_test_util.vcxproj.filters
+++ b/vsprojects/vcxproj/grpc_test_util/grpc_test_util.vcxproj.filters
@@ -313,6 +313,9 @@
     <ClCompile Include="$(SolutionDir)\..\src\core\lib\transport\connectivity_state.c">
       <Filter>src\core\lib\transport</Filter>
     </ClCompile>
+    <ClCompile Include="$(SolutionDir)\..\src\core\lib\transport\hashtable.c">
+      <Filter>src\core\lib\transport</Filter>
+    </ClCompile>
     <ClCompile Include="$(SolutionDir)\..\src\core\lib\transport\metadata.c">
       <Filter>src\core\lib\transport</Filter>
     </ClCompile>
@@ -680,6 +683,9 @@
     <ClInclude Include="$(SolutionDir)\..\src\core\lib\transport\connectivity_state.h">
       <Filter>src\core\lib\transport</Filter>
     </ClInclude>
+    <ClInclude Include="$(SolutionDir)\..\src\core\lib\transport\hashtable.h">
+      <Filter>src\core\lib\transport</Filter>
+    </ClInclude>
     <ClInclude Include="$(SolutionDir)\..\src\core\lib\transport\metadata.h">
       <Filter>src\core\lib\transport</Filter>
     </ClInclude>
diff --git a/vsprojects/vcxproj/grpc_unsecure/grpc_unsecure.vcxproj b/vsprojects/vcxproj/grpc_unsecure/grpc_unsecure.vcxproj
index be02a4fa92..09a1e2386d 100644
--- a/vsprojects/vcxproj/grpc_unsecure/grpc_unsecure.vcxproj
+++ b/vsprojects/vcxproj/grpc_unsecure/grpc_unsecure.vcxproj
@@ -362,6 +362,7 @@
     <ClInclude Include="$(SolutionDir)\..\src\core\lib\surface\server.h" />
     <ClInclude Include="$(SolutionDir)\..\src\core\lib\transport\byte_stream.h" />
     <ClInclude Include="$(SolutionDir)\..\src\core\lib\transport\connectivity_state.h" />
+    <ClInclude Include="$(SolutionDir)\..\src\core\lib\transport\hashtable.h" />
     <ClInclude Include="$(SolutionDir)\..\src\core\lib\transport\metadata.h" />
     <ClInclude Include="$(SolutionDir)\..\src\core\lib\transport\metadata_batch.h" />
     <ClInclude Include="$(SolutionDir)\..\src\core\lib\transport\static_metadata.h" />
@@ -604,6 +605,8 @@
     </ClCompile>
     <ClCompile Include="$(SolutionDir)\..\src\core\lib\transport\connectivity_state.c">
     </ClCompile>
+    <ClCompile Include="$(SolutionDir)\..\src\core\lib\transport\hashtable.c">
+    </ClCompile>
     <ClCompile Include="$(SolutionDir)\..\src\core\lib\transport\metadata.c">
     </ClCompile>
     <ClCompile Include="$(SolutionDir)\..\src\core\lib\transport\metadata_batch.c">
diff --git a/vsprojects/vcxproj/grpc_unsecure/grpc_unsecure.vcxproj.filters b/vsprojects/vcxproj/grpc_unsecure/grpc_unsecure.vcxproj.filters
index 482da9b984..df7a9b9b43 100644
--- a/vsprojects/vcxproj/grpc_unsecure/grpc_unsecure.vcxproj.filters
+++ b/vsprojects/vcxproj/grpc_unsecure/grpc_unsecure.vcxproj.filters
@@ -265,6 +265,9 @@
     <ClCompile Include="$(SolutionDir)\..\src\core\lib\transport\connectivity_state.c">
       <Filter>src\core\lib\transport</Filter>
     </ClCompile>
+    <ClCompile Include="$(SolutionDir)\..\src\core\lib\transport\hashtable.c">
+      <Filter>src\core\lib\transport</Filter>
+    </ClCompile>
     <ClCompile Include="$(SolutionDir)\..\src\core\lib\transport\metadata.c">
       <Filter>src\core\lib\transport</Filter>
     </ClCompile>
@@ -812,6 +815,9 @@
     <ClInclude Include="$(SolutionDir)\..\src\core\lib\transport\connectivity_state.h">
       <Filter>src\core\lib\transport</Filter>
     </ClInclude>
+    <ClInclude Include="$(SolutionDir)\..\src\core\lib\transport\hashtable.h">
+      <Filter>src\core\lib\transport</Filter>
+    </ClInclude>
     <ClInclude Include="$(SolutionDir)\..\src\core\lib\transport\metadata.h">
       <Filter>src\core\lib\transport</Filter>
     </ClInclude>