9
\$\begingroup\$

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.

\$\endgroup\$
1
  • \$\begingroup\$ There's 2 bugs in your StringBuilder version. If your string has this pattern: "key=&={Value2}", You should get key with an empty value and the empty key should be ignored. Your code assigns {value2} to key. Also it seems to miss the last key,value pair completely. \$\endgroup\$
    – user33306
    Sep 13, 2017 at 1:42

4 Answers 4

3
\$\begingroup\$

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.

\$\endgroup\$
4
  • 1
    \$\begingroup\$ Why do you decode the key and value separately instead of decoding the whole query ? It may be more efficient. \$\endgroup\$
    – gervais.b
    Sep 13, 2017 at 13:55
  • 1
    \$\begingroup\$ But it would be wrong. If the URL contains %26 anywhere, it would become ambiguous. See the third test case. \$\endgroup\$ Sep 13, 2017 at 13:56
  • 4
    \$\begingroup\$ @gervais.b To support what RolandIllig wrote, the standard explicitly says that it is wrong to decode before splitting up the URL for exactly the reason he has given: tools.ietf.org/html/rfc3986#section-2.4 \$\endgroup\$
    – pkeller
    Nov 29, 2018 at 11:09
  • \$\begingroup\$ this means percent-encoded parts are to be interpreted as literals, never as keywords, but that doesn't make a single pass tokenizer impossible \$\endgroup\$
    – dfhwze
    Aug 31, 2019 at 12:44
1
\$\begingroup\$

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

\$\endgroup\$
5
  • \$\begingroup\$ This answer doesn't handle percent encoding, but must do so. \$\endgroup\$ Sep 13, 2017 at 7:10
  • \$\begingroup\$ @RolandIllig you'r right. We can either decode the input before creating the matcher or improve the regex. I would prefer the decode solution. Anyway, the question don't say anything about encoding. (docs.oracle.com/javase/7/docs/api/java/net/URLDecoder.html) \$\endgroup\$
    – gervais.b
    Sep 13, 2017 at 7:25
  • \$\begingroup\$ The question mentions the word URL, and that alone makes percent-encoding a MUST requirement. Any code that "solves URL parsing" but doesn't do percent encoding is simply wrong. And wrong code should not be in a response to a code review request. \$\endgroup\$ Nov 29, 2018 at 21:52
  • \$\begingroup\$ @RolandIllig Would editing the answer to be correct code be better than putting someone on blast? Gervais.b offered solutions to how to improve on the answer and it looked like they wanted to know which one the asker's would prefer. \$\endgroup\$ Sep 19, 2019 at 20:00
  • \$\begingroup\$ I intentionally didn't edit the answer since that could have gone unnoticed by gervais.b. Instead I prefer that the author of buggy code should correct it as well. I already wrote the correct code in my own answer, therefore I don't see a reason to edit this answer to create duplicate code. \$\endgroup\$ Sep 20, 2019 at 13:27
1
\$\begingroup\$

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 => " 
\$\endgroup\$
6
  • \$\begingroup\$ This answer doesn't handle percent encoding, but must do so. \$\endgroup\$ Sep 13, 2017 at 7:11
  • \$\begingroup\$ What do you mean by that? \$\endgroup\$
    – user33306
    Sep 13, 2017 at 7:14
  • \$\begingroup\$ @RIllig - The OP says nothing about encoding only parsing a string. Imposing such restrictions is totally ridiculous. Especially when you don't offer anything better. \$\endgroup\$
    – user33306
    Sep 13, 2017 at 7:24
  • \$\begingroup\$ The title mentions the word URL. Everything else follows from that. \$\endgroup\$ Sep 13, 2017 at 7:29
  • \$\begingroup\$ The title says url query string which indicates it's already decoded. The encoding then becomes irrelevant. \$\endgroup\$
    – user33306
    Sep 13, 2017 at 7:32
0
\$\begingroup\$

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());
}
\$\endgroup\$
3
  • 1
    \$\begingroup\$ Did you mean to use & in Splitter.on(',')?. \$\endgroup\$
    – Tushar
    Oct 14, 2019 at 11:11
  • 1
    \$\begingroup\$ On code review we review the users code to suggest improvements, while your answer may provide an alternate solution it doesn't address the posters code. Is there any observations about the code in the question you can make? \$\endgroup\$
    – pacmaninbw
    Oct 14, 2019 at 14:45
  • \$\begingroup\$ @Tushar that's correct, amended \$\endgroup\$ Oct 15, 2019 at 10:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.