Splitting URL query string to key-value pairs

Question

I have a URL query string "key={value}&key2={value2}&key3={value3}" and have to produce a key-value pair of the string by splitting & and =. Also, I have to watch out for corner cases such that if a key isn't present do not add it to the hash map but if a value is missing the key can be added with an empty value. One way is to first split the string by & and finally by =. So this can be accomplished but having two passes. But I am attempting to accomplish this in one pass.

First idea: I came up with one pass using the split function, but it didn't account for corner cases.

public Map<String, String> splitString(String s) {
    // String s represents ParamAndMacro
    String[] split = s.split("=|\\&");
    int length = split.length;
    Map<String, String> maps = new HashMap<>();
    for (int i=0; i<length; i+=2){
          maps.put(split[i], split[i+1]);
     } 
    return maps;
}

Second idea: One pass with certain conditions and using StringBuilder:

public Map<String, String> splitString(String s){
 Map<String, String> maps = new HashMap<>();
 int length = s.length();
 StringBuilder sb = new StringBuilder();
 String key = "";
 String value = "";

char prev = ' ';
for (int i=0; i<length; i++) {
    char a = s.charAt(i);
    if ( a != '=' && a != '&' && prev != a) {
           sb.append(a);        
      }
    //finds a key
    else if( a == '=' && prev != a && prev != '&') {
          key = sb.toString();
          sb = new StringBuilder();
      }
    // finds a value and also ensuring a key is not empty
    else if (a=='&' && prev != a && prev != '=') {
          value = sb.toString();
          sb = new StringBuilder();
          maps.put(key, value);
            }
    // checks corner case to see if a value is empty
    else if (prev=='=' && a == '&') {
          value = "";
          maps.put(key, value);
          sb = new StringBuilder();
    }
   //how to check if a key is missing and skip to other pair

            prev = a;
    }
    return maps;
}

My concern is whether my code is efficient in terms of splitting and using StringBuilder. Please feel free to improve or give suggestions.

Answer 1

To decode the query string correctly, you must take care of percent-encoding, like %25 for a literal percent, or %C3%A4 for an ä (encoded as UTF-8). The canonical code for doing this is:

import java.io.UnsupportedEncodingException;
import java.net.URLDecoder;
import java.util.LinkedHashMap;
import java.util.Map;

public class QueryStringDecoder {

    public static Map<String, String> decodeQueryString(String query) {
        try {
            Map<String, String> params = new LinkedHashMap<>();
            for (String param : query.split("&")) {
                String[] keyValue = param.split("=", 2);
                String key = URLDecoder.decode(keyValue[0], "UTF-8");
                String value = keyValue.length > 1 ? URLDecoder.decode(keyValue[1], "UTF-8") : "";
                if (!key.isEmpty()) {
                    params.put(key, value);
                }
            }
            return params;
        } catch (UnsupportedEncodingException e) {
            throw new IllegalStateException(e); // Cannot happen with UTF-8 encoding.
        }
    }

    public static void main(String[] args) {
        System.out.println(decodeQueryString("&&&"));
        System.out.println(decodeQueryString("&&&a=b"));
        System.out.println(decodeQueryString("a=b&c=%26%25==&utf8=%E2%9C%93"));
        System.out.println(decodeQueryString("latin1=%FC"));
    }
}

I don't know why you prefer to do the parsing in a single pass. That would be possible, but the single-pass code must then behave exactly like the above code. Furthermore, since this part of the code is probably not the bottleneck, there is no point in optimizing it for execution speed instead of readability.

Answer 2

Low level parsing like you do with StringBuilder is usefull and certainly performant but no easy to understand. So it may be a bit too-much for such usage.

The split solution is more common. You can manage the corner cases with some index checks.

But I would suggest the usage of a regex. You can easily grab the idea without understanding the pattern :

String input = "key={value}&key2&key3={value3}";
Pattern pattern = Pattern.compile("(\\w+)=?([^&]+)?");
Matcher matcher = pattern.matcher(input);
while (matcher.find()) {
    System.out.println(" - Key   : "+matcher.group(1));
    System.out.println("   Value : "+matcher.group(2));
}


/* Output :
 - Key   : key
   Value : {value}
 - Key   : key2
   Value : null
 - Key   : key3
   Value : {value3}
*/

This one accept the missing values by returning null for matcher.group(2)

https://docs.oracle.com/javase/7/docs/api/java/util/regex/Pattern.html https://docs.oracle.com/javase/7/docs/api/java/util/regex/Matcher.html

Answer 3

Since none of the three solutions offered here cover all edge cases I'm submitting one that does and that should also be comparably performant:

public static Map<String, String> MakePairs(String input)
{
    Map<String, String> retVal = new HashMap<>();
    int fromIndex = 0;
    int toIndex = 0;
    while (toIndex != -1)
    {
        String key = "";
        String value = "";
        toIndex = input.indexOf('=', fromIndex);
        if (toIndex - fromIndex > 1)
        {
            key = input.substring(fromIndex, toIndex);
            fromIndex = toIndex + 1;
            toIndex = input.indexOf('&', fromIndex);
            if (toIndex == -1)
            {
                value = input.substring(fromIndex, input.length());
            } else
            {
                value = input.substring(fromIndex, toIndex);
            }
            retVal.put(key, value);
            fromIndex = toIndex + 1;
        } else
        {
            fromIndex = input.indexOf('&', toIndex) + 1;
        }
    }
    return retVal;
}

This code uses indexOf and substring rather than building strings with StringBuilder.

This sample string "mwpury={vkcc}&dygjqlodb={apgsbzfc}&iixmr={macwh}&elispjlxe={aicpwhcx}&uhourffuq=&={azphov}&xgsgamyzr={pukaj}&mksiicikq={diqoav}&fmmp=&yvlyuvuf={mmcpazepy}" produces this result:

[0] = (HashMap$Node) "mksiicikq => {diqoav}"    
[1] = (HashMap$Node) "dygjqlodb => {apgsbzfc}"  
[2] = (HashMap$Node) "iixmr => {macwh}" 
[3] = (HashMap$Node) "yvlyuvuf => {mmcpazepy}"  
[4] = (HashMap$Node) "xgsgamyzr => {pukaj}" 
[5] = (HashMap$Node) "mwpury => {vkcc}" 
[6] = (HashMap$Node) "uhourffuq => "    
[7] = (HashMap$Node) "elispjlxe => {aicpwhcx}"  
[8] = (HashMap$Node) "fmmp => " 

Answer 4

You can use guava's Splitter class, splitting on & and with key/value separator =. By looking at the source code it seems the split implementation is O(n):

import com.google.common.base.Splitter; 
import java.util.Map; 
import java.util.Map.Entry; 

...

String input = "key={value}&key2&key3={value3}";
Map<String, String>
        map
        = Splitter.on('&')
        .withKeyValueSeparator('=')
        .split(input);

// Looping over entries stored in map
for (Entry<String, String> entry : map.entrySet()) {

    // Displaying key and value pairs
    System.out.println(entry.getKey() + " -> "
            + entry.getValue());
}